I personally prefer virtual music jukebox - virtualmusicjukebox.com
It has had its issues in the past - I have used versions as old as 6.0 and now up to 9.xxx
Of all the designs and layouts I find this really to be the most simplistic and fairly most jukebox like for me..
Really if you are using a touch screen this setup is really nice.. lots of customizable options and overall just looks clean. It does not look like a windows app. I ran it for a while on my laptop - set it all up the way I wanted and then bought a copy for my desktop that is now my jukebox.
Once you have all the settings set the way you want them - you really can get this to be a fairly professional looking software.
in a real jukebox (the last few that I can recall seeing in a pizza hut) you dont have the skip, rewind bla bla bla options, and this software lets you turn those features off to your "guest" - they come in pick a song or 12million, they get queued up by the software - and the next one plays when the first one is done - just like real quarter eating jukeboxes..
The software supports money accepter options (if you choose to go this route)
I just really like the feel of this software - it shows covers you scroll through - hit the keys you want or tap the song.. presto it plays..
Try it out.. like Space fractal / denmark said - try them all and if you like one use it.
links to my *almost* finished project - just have to setup the bar in front of the screen and setup the user control panel for my friends to come in and tag some tunes!
http://www.lucky7dvds.com/jukebox