Whenever people discuss random playback of multimedia files online, I always see this same anecdote pop up: Apple wanted to add shuffle to iTunes, so an engineer made a perfectly random algorithm to serve up perfectly random tunes. Some time passes and users start to complain because the algorithm seems to have an affinity for certain songs that are played over and over while others languish, played only infrequently or even never. As the story goes, the algorithm is, of course, perfect, and the silly humans merely perceive patterns where none exist, like superstitious cavemen, and the ratio of plays would have tended toward 1.0 if they had just waited long enough and with a large enough sample size. So, our fabled engineer goes back to his perfectly random algorithm and makes it less random, but in a way that appeases the poor dumb-dumbs, and that's how we get iTunes' shuffle.
If you couldn't already tell, I think this anecdote is horseshit on several levels. Anyone that works with computers knows that producing true randomness is very hard to do (an entire branch of cryptology is devoted to this), and patterns in pseudo-random distributions tend to become more apparent with more samples, not less. Personally, I used iTunes' shuffle exclusively on a set of several thousand songs over the course of a few years, and it most definitely picked winners and losers, so Mr. Smug Engineer can get stuffed.
Nevertheless, the fact remains that if you randomly sample from a set (whether it's really random or pseudo-random), you're going to get repeats, and that's a drag when you feel like you're hearing the same songs (or watching the same rerun of your favorite show(s)) over and over. The solution to this problem is to use any ol' pseudo-random shuffle but ensure that each item is removed from the list of available items once it has been played until every item has been played. Rinse and repeat.
Plex has a way to do this, but it's not obvious, and it builds from their "smart playlist" feature. With this in mind, you would think 'step 1' would be to head over to the 'Playlists' page, but this is unintuitively not the case. No, you have to go to main page for the type of file you're wanting to randomize (in my case, TV shows):
and, if there are any tabs for "recommended", "library" and/or "playlists," again do the unintuitive thing and *do not* go to the "playlists" tab. Instead, go all the way to the left, where it says "All", click on it, and at the bottom of the menu that pops up, look for "custom filter...":
Here, you can use search terms and keywords to filter down to the criteria you need. For example, "show title" "contains" "Futurama":
Now, here's the important bit: click on the plus sign (+) in the circle on the far right, past your search field to add a new set of criteria. From here, instead of "show title", look for "unplayed episodes" and set the next field to "is true". Click on "save as" to give your playlist a title, and it will now appear in your playlists tab, with a little gear in the corner to denote that it's a dynamic "smart" playlist:
Now, when you go to play from the playlist, use the shuffle option and it will shuffle among the remaining unplayed episodes *only*. Eventually, you will exhaust the playlist and need to go back to the show and mark it as "unplayed" to refresh the pool of episodes.