There are specific applications available for generating random playlists continuously - typically used for automated radio broadcasts - but these often come at a premium. I had
Raduga running when I was doing student radio a few years ago for overnight playlisting, and it did the job, but I wouldn't consider it as easy to use as something like iTunes. Have a google for something like 'automated broadcast software' or 'automated radio playlists' and see if anything good comes up. I couldn't say what software would be best to go with currently, but be aware there are professional applications designed for this purpose.
However, if you are just looking for free consumer software, I'd also recommend going with iTunes. But I would say that it has a huge failing as far as being able to act as a fully-fledged jukebox for a media PC. Namely the narrow range of formats it supports. Personally I'd want my media PC to be able to play anything I can throw at it, be it FLAC, musepack, OGG, MP3, AAC and so on.
On balance it does have an excellent and intuitive interface for such a system, so if format support is not a priority then I'd say it was the best bet for the requirements. In particular, its Smart Playlists will be good for generating playlists that need to fit a particular mood or atmosphere without becoming stale.
It's a shame your media PC is XP-based, as I would say the ultimate free jukebox application is
Amarok. It's very similar to iTunes but frankly blows it out of the water. Supports the same kind of randomiser functions, playlisting but comes with way more format support (audio-engine dependent). If you get the chance, I highly recommend giving it a whirl. You can also run scripts internally, allowing you to automate pretty much anything e.g. scheduled playlisting.