If this should be marked Community Wiki, please let me know.

I'm switching from XP to Ubuntu, and I have been very disappointed with the selection of media players available. I'm primarily interested in an audio player, but integrated video and library management is OK, too. My criteria:

• Must be able to play audio CDs (I'm shocked how many apps this does away with, right away)
• Must be able to play MP3 & WAV; OGG, SHN, FLAC are all bonuses
• Repeat and Shuffle modes are a must
• FreeDB / GraceNote through a proxy is a must (if it can read a PAC file, that would be awesome)
• It needs to be really small, e.g. skinnable or an applet
• Ability to execute a playlist is a plus
• Gapless MP3 playback a plus

I'm running Gnome, but I'm not totally adverse to a KDE app. Command-line only is also a viable option.

Some that I've tried:

• RhythmBox - probably the best of the lot that I've tried; I don't like its mini mode (doesn't show the song being played) and I can't figure out how to get it to hit FreeDB/GraceNote through a proxy
• Songbird - can't play CDs, playlist management is atrocious
• Banshee
• Jajuk

Maybe a couple of more.

Thanks!

UPDATE

I tried out VLC, Amarok and Songbord (again). VLC I eventually got to work (I had some kind of bad configuration). It seemed way more involved than I was looking for out of a music player, and in general more geared to video than audio. I couldn't fathom its library management, which I think it has; maybe it doesn't, and that's why I couldn't figure it out.

Amaork looked very promising but the library management was not to my liking, and the way it handled a playlist with both MP3 and WAV is inexplicable at best. I did like some aspects of the UI, but not enough to keep it.

Songbird is very finicky, but I like the library management. Sort of. It kept telling me my Watch folder was invalid, even thought it clearly was accessible. Playlist management is bizarre, and the message that it was deleting source files whenever I deleted a playlist had me too worried to keep using it. Had it been able to play CDs, maybe I would have persevered.

Audacious, while a bit odd at times, does seem to do what I want. If it had a library manager, I wouldn't have bothered trying any of the others.

Thanks for the help, everyone!