Nearest neighbor search in latitude/longitude coordinates
First things first, if this is really a geography problem, then you probably don't want to calculate distances on the sphere, but rather on the reference ellipsoid. But even then, the reference ellipsoid is close enough to a sphere that it works as an approximation, and then accurate distances can be computed as appropriate.
You've already worked out that if all you need is nearest neighbour on points, then using 3D distance as a proxy for great circle distance is probably the most efficient approach. To be honest, this is probably the best solution for your specific problem, but not if you had to do distance queries involving non-point geometry (e.g. &quot;find me all lines within 200km of this point&quot;).
The usual practice for spatial indexing in GIS is to use some variant on a bounding volume hierarchy.
In Cartesian space, that would mean an R-tree, and in geographic space, you would use circles of a sphere or ellipsoid as the bounding volume shape. In the case of a binary tree index, you can use a great circle as the splitting criteria for each node.