You just need "distance" in the k means to be more general than just using the euclidean distance between coordinates, you need a norm appropriate for the space you are working in. Haversine distance should be fine for this application.
Yes, but that's harder to implement.
Spherical kmeans is much simpler. A simple cos distance between vectors.
I don't remember exactly what I did or how it maps to spherical k-means. One modification was to use a version of the k-means algorithm but doing clustering not by fixed size but by fixed distance. The other was measuring distance by what the map coordinates would be rather than the lat/long coordinates. The last thing was rather than using a euclidean distance which gives circular neighborhoods, we used max(∆x, ∆y) which gives square neighborhoods. Clusters were pre-calculated or else we would have made rectangular neighborhoods with the proportions of the viewport window on the map. In retrospect, it might have made sense to do client-side clustering for more detailed zoom levels where n would have been relatively small and we could have gotten that as well.