The thing worth keeping in mind here is that while there are a lot of great music players on Linux, most haven't been made with a portable device in mind--they are expecting you to use a mouse and a keyboard on a 1024x768+ screen.
For instance, I still prefer xmms and xmms-like MP3 players on...