I use iTunes DJ pretty frequently, it serves a great purpose for when you have no specific artist/album you wish to listen to, nor a loose collection of songs based around a single genre (Genius).
This issue is at it's worst when I'm driving, and wish to listen to music; Voice Command only gives me the ability to pick an artist, album, or playlist.
How best am I able to create something which uses my entire Music library, and can quickly, easy, and perhaps most important of all, safely, begin playing any random item?
Additionally, shuffle should be turned on, or some other aspect of randomization should be used as part of the accepted solution. One other important aspect is that I've explicitly mentioned the use of Voice Command, which only exists on an iPhone (3GS and 4).