It was actually showing "Random" despite the block title.
Need to check a few other things with widgets. Particularly the fact that I have been noticing a pattern of the images always being particularly old and usually grouped rather than appearing to be random (such as in the example above).
Ah yeah, it was consistently showing the same images (oddly enough IDs 3 - 7 or 8 or so). Checked mobile and they're different so I guess it just appeared to be showing them in the wrong order, guessing it caches this per session?
Edit: Different now on macbook too, but same images as mobile so I guess it's cached globally
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.