Eu tenho um MP5 que quebra um galho nas viagens, mas é meio chato quanto à compatibilidade dos videos.

Aqui vai minha solução para mandar videos do youtube para ele.

Instalação:

wget http://g1mr.com/debian/utbload_1.1-1_all.deb
sudo apt-get install mencoder youtube-dl
sudo dpkg -i utbload_1.1-1_all.deb

1. Baixe o arquivo utbload
2. Salve-o como  /usr/bin/utbload ( sudo cp utbload /usr/bin/ ) 
3. sudo apt-get install mencoder youtube-dl wget
4. sudo +x /usr/bin/utbload

Uso:
utbload <video_url> <nome para o arquivo>

Exemplo:
utbload "http://www.youtube.com/watch?v=9kQcYENQW_A" MyVideo

Novo:

Formato para iphone, use:

utbload "http://www.vimeo.com/2373142"  MyVideo iphone

Veja o resultado em sua pasta ~/Videos/utbload

Obs: O formato do video gerado é compatível com muita coisa mas usa uns 30% a mais de espaço que o formato .flv
Se o seu player roda flv ou mp4, apenas use o aplicativo youtube-dl

Atualização em 15/09/2010:

utbload agora consegue fazer o download de videos do Vimeo.
Source:  http://bazaar.launchpad.net/~g-g1mr/%2Bjunk/tools/annotate/head%3A/utbload