NavList:

Sean, you wrote:
"That is ... until I realized that I was essentially looking at an equirectangular projection. When wrapped onto a globe, the higher latitude points would be condensed due to the decreased spacing in longitude."

Yes. That's exactly right. There are a number of ways to distribute random points uniformly on a sphere. The modification of your map below illustrates how to do this with a simple sinusoidal projection of the globe. The sinusoidal is the easiest equal-area projection. I'm only including half, but it's easy to see how to extend it. 

We're throwing darts at a dartboard. To model darts thrown at a circular dartboard, we put a square frame around it, and randomly generate uniformly-distributed x,y pairs in the square. That's easy. Then calculate r, distance from the center of the square, for each pair and discard any points that have r>R, where R is the radius of the dartboard. You now have points randomly distributed in a circle (not quite the same as a random dart game, but a good starting point --see my last comment below). Similarly with the sinusoidal projection, we generate points as uniformly-distributed x,y pairs with both in the range from -90 to +90, and throw out any that fall outside the sine-curve arc that makes the right-hand limit of the map projection. The rule for this is simple: if x>90·cos(y), reject the point. Then y is equivalent to latitude, while x must be mapped onto longitude:
   Lat = y,
   Lon = 2·x/cos(y).
The factor of two doubles the range of longitude to cover both hemispheres.

Notice that about 35% of the random points fall to the right of the sine-curve arc and are rejected. Discarding randomly-generated points is no great cost today, but on a very slow device like a programmable calculator, as in the application originally suggested here by Marco Costa, generating randoms can still be time-consuming, and in that case an algorithm that uses all random points is preferred. Except for this hobbyist application on calculators, computation is now so cheap that no one in their right mind worries about throwing away points like this.

On a more practical note, the idea that we "simulate" celestial navigation scenarios by uniformly distributing points over the entire globe is a mathematical idealization --a good starting point, but no more, like the darts uniformly distributed on the circular dartboard. Instead one should use a point-density function that correponds to the actual probability of applying these methods in some band of latitude. Where do most ships sail? Or if you're pondering aerial solutions, where do most aircraft fly? It's also interesting to note that your original map, which yields a much higher density of random points near the poles, does apply reasonably well to one case of vehicle density, namely satellites in orbit. Since most satellites are in nearly polar orbits, there is a "traffic jam" of particle density above high latitudes. 

Frank Reed
Clockwork Mapping / ReedNavigation.com
Conanicut Island USA

File: