...wrong extension, and it turns out this is even more confusing than I thought.

Core has had a Special:RandomInCategory, written by the one and only @Bawolff, since ed1c89b88454744d0ae08e7048992f80920276d8 (1 August 2013/MW 1.22.0).

VasilievVV wrote (and @Reedy contributed to) an extension with the same name, based on core SpecialRandompage.php code, originally back in December 2007 (or even earlier).

tl,dr: mw:Extension:Random In Category#Comparison to Core; performance and biasedness of the results (as well as the special page name, and intentionally so). However, it should also be noted that the extension sadly appears somewhat unmaintained for the special page is using globals where it should be using RequestContext and there is no extension.json file but rather a PHP entry point. (These issues are simple enough to resolve and shouldn't take more than a few minutes to fix.)

...I don't actually understand what that means in practice, so I'll just ask: What do we do to give our users a consistent or improved experience with whatever it is these things do while also optimising efficiency and reliability with a better backend?

Honestly, probably better to use the extension if it still works, uncyclomedia probably doesn't have big enough categories to matter.

The core special page is based around the constraint of what can I easily get enabled on wikipedia. (I almost wonder if it should use an unbiased mechanism [extension goes with join to page_random. I would probably just do rand()] when MiserMode is false).

Can someone please edit the task summary and summarize whatever bug or feature this task is about? Thanks.

Okay, I think we've actually resolved that question now, so back to meaningful task summaries!

Change 501338 had a related patch set uploaded (by Jack Phoenix; owner: Jack Phoenix):
[mediawiki/extensions/RandomInCategory@master] RequestContext + extension registration support

https://gerrit.wikimedia.org/r/501338

Change 501338 merged by jenkins-bot:
[mediawiki/extensions/RandomInCategory@master] RequestContext + extension registration support

https://gerrit.wikimedia.org/r/501338