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.

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.