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...":