This is the solution I arrived at, too: explicitly balance out the bias, which seems to be as simple as just taking the square root. Surprised the whole thread isn't full of that idea.

Long rambling version:

The bias in the naive 'solution' is demonstrated in that if we consider a circle of radius 0.5, it has an area of 1/4 that of a circle with radius 1, not half. Which means that as we span our random parameter between 0 and 1, we 'spend too much time' in that small 'inner circle'.

(It's easiest to assume a circle of radius 1, centred about the origin. Nothing interesting arises from additional generality.)

So we don't want the displacement from the origin to rise linearly with the uniform-random parameter. Instead we want the area of our 'inner circle' to rise linearly. Which means that the displacement from the origin should be the square root of the random parameter. (The random parameter's interval will have to be adjusted appropriately of course.)

Our 'theta' has no bias trouble. Transforming from number (angle) into vector/coordinate form, is just routine trig. Nothing interesting to worry about there.

All that's left is to be careful that our theta span the interval [0, 2 * pi) (carefully excluding 2pi), whereas our area should span [0, pi * r^2] (inclusive, assuming that our 'circle' is meant to be an 'open ball' rather than a closed one).

Either we're missing something, or this Haversine business is a needlessly complex answer here.

I considered that another approach might be to define a spiral that 'winds through' all points in the circle, but I'm pretty sure that's not possible. If it were possible, it would give an injective space-filling curve, which is known not to exist. (If it were not injective, it would presumably be biased and so be a non-answer to our question.) Put another way, if your answer involves accepting just one random number, and not two, then your answer is necessarily wrong. (I think I'm getting all this right.) [0]

Another thought: the naive solution is biased despite being injective. Interesting. That seems to be the root of the failure of intuition that leads us to the naive (biased) 'solution'.

[0] https://en.wikipedia.org/w/index.php?title=Space-filling_cur...