First the basics: Starting from a playlist, just click the shuffle icon (the intersecting arrows) in the header of the playlist view, not the shuffle icon in the iTunes LCD. However, there is no shuffle icon when you view your entire music library, so you'll have to fake it by creating a smart playlist with the condition "Media kind is music," with live updating turned on.
Click list icon at the right of the iTunes LCD to view the Up Next queue. The clock icon in that list shows recently played tracks, like the dimmed portion of the old iTunes DJ interface. You can re-order songs in Up Next by dragging them around, and new items can be added to the top of the queue form anywhere in your library using the contextual menu, just like you could in iTunes 10, or by clicking the > icon that displays when you hover your cursor over a track.
What may not be obvious is how to replicate the function of the Refresh button. To do this, click the shuffle icon in the header of your playlist view again.
Now for the caveats:
- Clicking that shuffle icon again stops the currently playing song, rather than creating a new queue as iTunes DJ did.
- You have to click on the Up Next list icon again to see the results (or use the new Command-Option-U shortcut), rather than them being immediately visible.
- Even with shuffle set to songs (Controls > Shuffle > By Songs), you will still see tracks from the same album show up in the list in sequence fairly often. There used to be a way to control this, but I've forgotten and can't seem to find it now.
[kirkmc adds: I was initially very confused by Up Next, but I've figured it out, and it's quite practical for queuing up music. However, you can only see 20 songs in the queue, which can be a bit limiting. So it's not a real replacement for iTunes DJ, and this hint does help a bit. Personally, I never used it to play music from my entire library, so the current implementation works for me.]

