I've used IMMS (http://www.luminal.org/wiki/index.php/IMMS/IMMS) with xmms and have liked the way it picks the songs for me. Basically, it monitors your listening habits and learns from your behavior. If you're always skipping certain songs, it will not play them as often. It keeps track of when you last listened to songs and thus does a very good job at shuffling (keeping in mind frequency of play with aforementioned song ratings). It uses a variety of techniques to figure out which songs should be played together, and which should not. It studies your listening habits, as well as using acoustic properties of the songs themselves, such as BPM and frequency spectrum. The main point is that this is all done transparently so you dont have to waste time organizing, rating, etc while listening to music. See the link for more info.
This ticket was migrated from the old trac: re #425