I'm very partial to Quod Libet. It is utterly flexible and has probably the most powerful tagging engine of any media player. Customizing it just right takes a little bit of work and is a little bit arcane, but once it's there, navigating a huge library of music is completely fluid and intuitive.
I don't play music from my Linux machine often, but when I do it's from deadbeef. Big view of the current playlist, tabs for others and keyboard shortcuts for playback control works for me.
http://deadbeef.sourceforge.net/