I came here, frustrated for the same reasons as you. Having bought a new MacbookPro I now have to live with iTunes 11 and the loss of iTunes DJ is had to cope with.
I actually never used iTunes for anything BUT syncing randomised playlists to my iPhone. I have about 35 000 songs and I liked the feature of having the computer randomly select which songs to transfer. I was being constantly suprised by songs choices I would never have made myself.
I have found a workaround by using some of the tips in this thread. Here's what I have found...
1/ I created a smart playlist set up as follows (excuse me if I get the exact names wrong, my iTunes is in Swedish) I ticked the box in the upper left corner ("similar conditions"?) I set as a single condition that the playlist should pick songs from "music". I limited the number of songs to 35 000 and then selected "random" in the last box. I also ticked the "live update" box. I called this playlist "shuffled".
2/ Once I clicked OK I sorted by clicking the number column, next to "names". I now had a shuffled playlist containing all of the music in my library.
3/ I then created another smart playlist and set it up as follows: I ticked the same upper left box and set as a single condition that the playlist should pick songs from the playlist called "shuffled", i.e. the playlist I just created. I limited the number of songs to 100 as this is enough for me to last a while on my iphone. I also ticked the "live update" box here. Quite important, I think, for this particular playlist. I called this playlist "random".
4/ This only has to be done once and doesn't really take that long. The trick now is to update/refresh the "random"-playlist and here's how I did this: I selected the playlist called "shuffled" and chose to edit it. I changed the number of tracks from 35 000 to 1 and hit OK. I then changed it back to 35 000 and hit OK. This little manouver refreshed the "random"-playlist which now contained 100 new tracks, so to speak.
I hope I have explained it well enough. It's not as easy as before but almost.
God, I really, really have come to hate Apple. I weened myself off PCs back in the early 90s in order to take advantage of Mac-based pro apps like Avid and Final Cut Pro. Fast forward to now, and it all seems like a decades long conspiracy to just plain p**s me off.
I already hated iTunes 11 for not letting me look at two playlists side by side, one of the most common resources I used for creating new lists. Now I find I can't create shuffled lists, I can only play back shuffled?
This has really annoyed me. I cannot understand how it is an improvement to not be able to do what you did before. I used the shuffle feature quite often, in order to make large playlists which I then refined. After reading these posts, here is how I made a fifteen hour playlist for every day of the week.
1. Made a plalyist called "big" containing 2100 arranged in genre order.
2. Selected entire list and went to "info" and filled the comments section with "big playlist"
3. Went to "new smart playlist"
4. Selected "Limit to 2100 items" - "Comments contains "big playlist"" - selected by "random"
I now had a smart playlist called "big" which was listed randomly, when I clicked the numbers column.
I selected the first 300 items and put them into a playlist called "Monday" etc. etc.
Works fine for me.
<Just notice that someone beat me to this one - so this is a duplicate. Leaving it in having two descriptions is helpful.>
I'm using iTunes 184.108.40.206, but I think this work-around applies to other releases.
1) Create a non-smart playlist of the songs you want to randomize.
2) Create a smart playlist.
2a) Add as criteria, "Playlist is <name of playlist from step 1>
2b) Click "Limit to" checkbox.  items, selected by [random]. Click OK
The smart playlist now has the contents of the first playlist, but in random order. If you want, you can copy the contents of the smart playlist into a non-smart playlist, to keep the order from updating. Or you can play with the "Live Updating" setting in the smart playlist.
You don't have to do all three steps each time. Just replace the contents of the first playlist, and update the second playlist.
This is a lot of hassel for something that should be easy - but it worked for me.
JD & Colonel Hall,
Thanks for replying.
Right, well... Because it now looks like I will have to accept iTunes 11 in the near future if I want to upgrade to Mavericks, I installed '11 on the Windows side of my Mac to give your solutions a trial.
(I'm still not ready to install it on the Mac side yet; that is remaining on iTunes 10.7 for now...)
And I have to say that it does seem to do the trick, so perhaps I'm not quite so scared of upgrading to Mavericks.
I haven't yet actually synced my iPod to it, but I assume that the smart playlists do indeed arrive on there in shuffled order?
Having said that, I still intend to keep submitting repeated feedback requests to Apple for the shuffle button to be put back at the bottom of the sidebar. It was so much simpler when it was there, and surely it cannot be terribly advanced code-writing to just put it back?
Thank you so much for this solution, battiman! That worked for me. Apple really frustrated me taking away the randomize playlist feature. Unless, I'm listening to an album (which isn't often), randomized playlists (which usually numbers over 200 songs) with the shuffle feature turned off is literally the only way I listen to music in iTunes and on my iPod Touch. Like you, the only reason I used iTunes was to randomize playlists to play on my iPod.
I noticed the shuffe feature will favor some songs over others and almost completely ignore other songs. The result is you keep hearing the same few songs over and over more than others in the playlist. That annoys me to no end. On my iPod, I never play large playlists with the shuffle feature turned on. Randomizing the order is much better in order to hear every song in the playlist and like you said, you can also get surprised with a song you hadn't heard in a while. I had avoided updating to iTunes 11 from iTunes 10 because Apple discontinued the randomize playlist order feature when pressing shuffle in Tunes. But today I updated iTunes on accident and now I have iTunes 11. Thank goodness I found your post!
Only change I made to your method was in step 4, putting 0 instead of 1 because I noticed otherwise iTunes will start the playlist with the same song even though the ones after it will be random. Putting in 0 and then changing it back to your total song count starts the playlist off with a different song every time you randomize. Thanks again! I was about to go through the process of downgrading to iTunes 10 and reimporting my library from my iPod using CopyTrans when I found your post. Now I think I can live with iTunes 11 for now, but Apple really needs to bring back the simple randomize via click of a single button instead of hiding the feature away in smart playlists options with a not so obvious workaround.
Here we are, over 2 years later, and this problem still isn't fixed! It's frustrating, Steve, to see people giving the same answers over and over, as if you don't know what you're talking about. I HAVE BEEN SO ****** ABOUT THIS AND TOTALLY KNOW EXACTLY WHAT YOU'RE TALKING ABOUT!! I only use iTunes as a way to sync shuffled playlists to my ipod classic. I rarely listen on my desktop. I feel like all these remedies are from "techie" people, which I am not! I would love to go back to version 10.7 and never upgrade iTunes again, but I'm afraid I'm going to really mess it up, so I don't mess with it. Has anyone found an easier way? A way that doesn't involve making several more playlists (I already have so many). It sounds like I need to make 2 playlists for every ONE that I want shuffled. It's just crazy! Why hasn't Apple even responded to this? This "thread" of people can't be the only ones who have questioned this! Anyway... just wanted to vent here. I've read this thread several times over the years trying to bite the bullet and try some of these remedies, but then I just get frustrated all over again and say FORGET IT! Have you just given in and used the work-around, or are you doing something different? Thanks for listening...