hello everyone, i'm on a similar quest.
have been comparing many mid-range audio only players. except the daemon-based players (mpd and xmms2) - couldn't set them up.
and some others probably.
i had been using gmusicbrowser which was just perfect but sadly it didn't work well with my old external ntfs (windows) hard drive which hosts most of my music.

@demonboy (if you're still around), clementine covers ALL your points - i think you really want to check if you got the newest version (1.0.1). there's a ppa.
also it plays everything. had to install some gstreamer plugins, but it politely told me what's missing.

guayadeque is version 0.3.5 now, my second favorite. you can drag ui elements around. it plays everything. seems a bit heavier and slower than clementine.

also exaile, which has a slightly cramped and less customizable layout, but it's all there.

foobnix feels slightly buggy; it crashed once when i tried to open a russian radio station, but not a second time. also i don't like that it claims to be "like foobar2000". it's an exaggeration.

those players are simpler in my opinion because they lack some managing capabilities:

deadbeef is good, simple, quick. feels well made & robust. doubleplus: the equalizer can be integrated in the gui. probably my new ad-hoc player.
decibel is a bit bare and not very fast for being one of the simple players.
listen has some really nice features (now playing window with different colors, dynamic playlist filling), but is also missing some (no file browser, static columns). but i like it somehow.

all players take ~20% cpu (2GHz) whilst playing, but they are very different at startup, browsing, updating.


ultimateplayer and clementine are identical? why?

if you're interested in new command line ways of approaching your music collection, you might want to take a look at this.

ps: some players use qt4 for creating gui's (instead of gtk) which can look rather ugly. there's qtconfig-qt4 for customizing that (which is called qt4-qtconfig in the repos