There's a cache of media IDs stored in the simple cache. The cache is generated by Cron entry periodically. It was caching up to 300 media IDs in a pseudo-random sort of way. It performs X iterations getting Y media IDs per turn based on a randomly generated offset.
We've bumped that value up to 500 media IDs and made a few more adjustments so that out of that pool the media IDs selected from that will seem more random and with the increased pool hopefully we won't frequently hit the same albums over and over.
Of course the system isn't perfect, but its performance is much better. This is all because the performance of MySQLs RAND function is terrible. The random stuff will definitely work a lot better on larger galleries. The general advice would be to switch it off if the "random" results are seeming too repetitive. There's also cases where the number of items shown can be much less than you specified.
I've re-enabled random media here (with a better title) and it does seem a little bit more random IMO.