I'm currently using xmms2. Many of the powerful features it (will) provides are at development, but it's really usable ATM. It currently has nice playlist, collection, medialib querying possibilities (it wins where mpd lacks). CLI 'official' interface (xmms2) is being rewritting to something (still) better (korving).
From time to time I still switch back to mpd/mpc||ncmpc (or Quodlibet when on GUI).
As for the 'random album' playback feature (something like new cmus' lqueue, quodlibet's random album...):
- MPD: None of the clients I know has it, but there are two little pieces of C code that provide it:
http://www.musicpd.org/forum/index.php?topic=1389.0
- xmms2: It will be doable with the great playlist-collection features management system it will provide. I've written a poor, hackish shell script to get it in the meanwhile:
http://wiki.xmms2.xmms.se/index.php/Contribs