Bug 25931[1], "Implement efficient way to select random page from specified category on Wikimedia wikis" has just been marked as resolved, thanks to this patch[2] from Bawolff that Brion merged.
Yay! :)
[1]: https://bugzilla.wikimedia.org/show_bug.cgi?id=25931 [2]: https://gerrit.wikimedia.org/r/#/c/71997/