I'm quite an avid music listener, and my tastes are quite varied. I listen to everything from The Matrix Reloaded Soundtrack (playing now), to Israeli dance music, to Pop and Hip-Hop, and on to Trance. Given this, having all my music on the computer is far easier than shuffling CDs around, but even on the computer it can be difficult to manage several thousand different songs.
XMMS used to be my music player of choice, but its playlist manager is not quite up to task. It's impossible to search, and having multiple playlists isn't easy. I've just started using Rhythmbox, and it is better than XMMS. Rhythmbox keeps track of when a song was last played and you can give songs ratings. I would still like to see something like XMMS's queing feature that allows you to queue the next song after which it will go back to playing the playlist in the previous order. Also, I would like to see the random play mode having a weightings feature. For example, give a greater weight to songs not played in a certain amount of time; give a smaller weight to low rated songs, etc.