XMMS2 Command line music player
 

Xmms2 (client/server model) just made it into the Debian archives, so I guess it's getting close to ready. Seems to only include a command line interface at this point, but by the looks of their home page they have big plans. I installed it and found it pretty easy to get tunes playing. Haven't messed with it much, but I assume that it'll be real useful to set up playlists using wildcards against my various music folders and that sort of thing.

Hopefully, I'll eventually be able to figure out how to use it like a shoutcast or icecast stream.

I love xmms2 - I've been using it since I found it in the Arch User Repos about 3 months ago. Granted it has some kinks (I would love if it would stop playback when the GUI frontend I use is closed...but thats a problem with the frontend, not XMMS2)

Oh - and the frontends are easy to get installed and from what I can tell you will need to install them yourself, as the client probably won't ship with a GUI. Check out Shellac, gXMMS2, and all of the others!