We've always been fond of Amarok. It has some good features, nice add-ons, and felt just a little friendlier than some other Linux media players. We recently discovered a contender to the title of most loved Linux media player, the ominously named Banshee. Fortunately, Banshee doesn't involve listening to shrieking demons, unless that's your genre of choice.
It's an application that has been increasingly packaged with distributions that include GNOME as the default desktop. For those distributions that don't include it on a standard install, it's almost always available from a repository. Many of those repositories include, at present, Banshee's 0.13.3 version. This is the stable version of Banshee and shows loads of promise, but it isn't quite Amarok.