I've tried almost every single player out there. I still will install new players to test them out to see what they do. But I completely swear by
JRiver Media Center. It is killer for organizing all kinds of media--especially large libraries (I have over 40,000 songs at this point). I use it for video somewhat, but it is all I use for audio. Unfortunately it's only available for Windows (it's what's keeping me from going 100% Linux).
If you look through the Wikipedia article (linked to earlier in this thread) comparing music players, take a look at the features for JRMC. It's one of the only ones that's completely green for features AND audio format support (and is mostly green for a bunch of others). LastFM support isn't built in, but there is a plug-in that works great.
I'm also very visual. I like to look through the album covers to find music, rather than just looking at text and tags. JRMC has robust cover art support for browsing.
The bad news is...it ain't cheap (about $40). But they're constantly updating it, adding features, etc.
I HIGHLY recommend it....