...I've tried all the major ones.
Virtual Music JukeboxDigital JukeboxMusicmatchWinampeJukebox (a winamp component)
I just want to say I'm NOT trying bash any software at all. I support all of these programs, especially the first 2.
They all have drawbacks - but they all have some great features too.
I like VMJ for it's album displays and touchscreen-like interface. Very user friendly. Can't read MP3 embedded album art - I'm not about to create artwork (or find each one) for my collection.
Almost a requirement to use the program - browse by album art is it's major feature. Good product support.
DJ - probably the easiest to setup. And the quickest to load - pretty much the simplest interface for a party: available songs on the left, queue on the right. Some cool features like no repeat in queue and scrolling ID info. Can display album art, but also cannot access embedded artwork. No pause, though. Can't really resize anything, and the 'radio' (shuffle) mode doesn't really randomize the songs well. The same ones are always picked in 'random' order. Good product support.
Musicmatch - There are skins that can make it look not so...musicmatch-ish. Decent interface. 8.0 is bug-riddled though so steer clear. downloads album art automatically. By far the coolest feature is Supertagging. Slow, but handy for badly-ripped songs. It's a huge resource hog compared to the other 3. With a large collection it's almost impossible sometimes to move around in it. I concede that it's a much broader program and can rip and encode. It's not very user friendly. Haven't even tried product support because I have no interest in using it full time.
Winamp. It's winamp. Everybody knows winamp. Though with winamp3 most of my skins only half work now because they have a 'playlist editor'. The whole thing is a little too small for me. But it's small and plays smooth...works best with....
...eJukebox. The interface is downright ugly, but it makes up for it in features. I totally dig the kiosk mode, where it locks up fullscreen and all people can do is add songs. Very nice 'top 10' type lists and it downloads the album art automatically. Very intuitive browsing window and it looks pretty good at 800x600. By far the coolest feature is it's web interface, where you can access the jukebox from another computer on your LAN (or with a good IP). Control volume, playlist, see the album, search for song artist album etc. Here's a screenshot:

It has come in handy while I'm on my real computer surfing/working/etc and can change the playlists and songs on my cab (where my real collection is) without having to get up and walk to the living room. Cause I'm lazy

We'll see how it works out in a few months of use...but thought I'd post my impressions. I also have tried a bunch of tagging software, but let's not get into that nightmare

I welcome any corrections, software additions and such. I don't want to turn it into a battle if I can help it. I apologize for the length, and thanks for reading!