I own a Sony Walkman NWZ-S639F. It's a great mp3 player possibly much better than the ipod itself. Best of all it integrates well with Linux without needing any extra libraries or software. Rhythmbox can be used for syncing music files from my computer to the Walkman and Nautilus can be used to simply drag and drop pictures or videos.
When copying videos however, the Walkman is only capable of playing mp4 files of size 320x240. It also needs a jpg file of the same size and name as the mp4 file to display a nice thumbnail in the player interface. ffmpeg can be used to achieve all this very simply.
To convert a flv video downloaded from the internet to Walkman compatible video:
ffmpeg -i video.flv -s 320x240 -ac 2 video.mp4
To generate the thumbnail:
ffmpeg -i video.flv -s 320x240 -an -ss 00:01:00 -r 1 -vframes 1 video.jpg
All that is left now is to copy the generated mp4 file and the jpg file to the video folder in your Walkman.