I always used Winamp on Windows, so when I switched to Linux I tried basically every single open-source alternative that worked with my workflow: Per-song ratings, a nested Genre/Artist/Album/Song library browser, global hotkeys, able to handle a collection of >100 GB and a useful playlist/queue system.
It probably lacks some of the advanced stuff you would want, but I use it as I still do with Winamp: setup keyboard hotkeys to execute audacious -[rft] (skip around in songs from any app), load a folder (or folders) of songs and play them. Throw on ProjectM and you have a poor man's substitute for Milkdrop. And there's Shoutcast support as well.
The UI runs in skinned mode (pictured above) or in a more traditional mode that doesn't look out of place on your desktop.
MPD is pretty popular too http://www.musicpd.org/
It has a client/server model and you can create your own music streaming service by controlling it remotely and streaming back over http.
ncmpc/ncmpcpp is a client for mpd that resembles cmus quite a lot.
I use cmus too. For those who don't know it is a command line music player with a VIM-like command line interface ("/" to search, ":set x=x" to set various options).
For anyone else looking for the same thing: the one that I ended up choosing was http://gmusicbrowser.org/. See http://gmusicbrowser.org/screenshots/ListsLibraryContext.png.