Otdfbt

The obvious solution of Lattitude & Longitude doesn't work because it generates points more densely near the poles, and the other thing I came up with (Pick a random point in the unit cube, if it's in the unit sphere map it to the surface, and restart if it's outside) doesn't always find a point within a fixed number of tries.

The Lambert cylindrical equal area projection maps the sphere to a cylinder, area to equal area. It is easy to generate a uniform distribution on a cylinder. Simply map it back to the sphere.

For $(u_1,u_2)$ uniform on $[0,1]^2$, either

$mathrmlat=arcsin(2u_1-1),mathrmlon=2pi u_2$

or

$z=2u_1-1,x=sqrt1-z^2cos(2pi u_2),y=sqrt1-z^2sin(2pi u_2)$

Your method, even though it doesn't finish in a fixed number of times, is a reasonable way to do it. Each trial succeeds with probability $fracpi6$, which is better than $frac12$: the average number of trials is less than $2$.

Another standard method is to use the normal distribution. Generate $x, y, z$ independently from a standard normal distribution, then take the point $(x,y,z)$ and divide it by $sqrtx^2+y^2+z^2$ as you did for points inside the cube. The multivariate normal distribution is rotationally symmetric, so this will get you evenly distributed points on the sphere.

(The Box–Muller transform is one way to generate normally distributed random numbers, and some versions of it do not use rejection sampling, so they can be done with a "fixed amount" of randomness.)

Is there a way to generate uniformly distributed points on a sphere from a fixed amount of random real numbers per point?

This Stack Overflow answer mentions the Fibonacci sphere algorithm, and the currently unanswered Math SE question Is the Fibonacci lattice the very best way to evenly distribute N points on a sphere? So far it seems that it is the best? contains several excellent links in the question and in comments.

The method is deterministic, using either zero or one random number, no matter the number of points generated.

Florida State University's John Burkardt's web page Fibonacci Spiral Grid on a Sphere provides some references and examples of code implementations.

Edward Saff, Arno Kuijlaars,
Distributing Many Points on a Sphere,
The Mathematical Intelligencer,
Volume 19, Number 1, 1997, pages 5-11.

Richard Swinbank, James Purser,
Fibonacci grids: A novel approach to global modelling,
Quarterly Journal of the Royal Meteorological Society,
Volume 132, Number 619, July 2006 Part B, pages 1769-1793.

Extreme Learning's Evenly distributing points on a sphere addresses several criteria for judging the level of uniformity provided by different solutions, and describes the process of first generating a Fibonacci grid and then transforming it to a sphere.

An example of these Fibonacci Grids is shown below. These points sets can be transformed to a well-known Fibonacci spirals via the transformation

I can't be sure it will be sufficiently uniform for you, but it certainly looks nice!

Source

You can still use the longitude/latitude method. You just need to transform the latitude such that the probability of falling in any given latitude band is proportional to its surface area.

The length of the circumference at a latitude, l, is proportional to cos(l). (0 at -90 degrees, max at the equator, 0 at +90 degrees). Therefore, by integrating we know that the total surface area between any two latitudes, l1 and l2, is proportional to sin(l2) - sin(l1).

By inverting that, we arrive at a formula for transforming a [0, 1] uniform random variable (X) into a latitude such that any point on the sphere is equally likely to be selected:

latitude = arcsin(2X - 1)

Your second method can be improved in this way: Select the three coordinates (x, y, z) in a linear distribution from -1 to 1.

If (y * y + z * z) > 1, select replacements for these two only. (You will only have to re-roll them 4-pi/4 (roughly 21.4%) of the time; average random numbers used is 1 + 8/pi = ~ 3.546.

Keep x as it is, scale both y and z by sqrt((1 - x * x)/(y * y + z * z)).