I'm glad you like the idea. Maybe after it would work here I can go lobbying to badgegen :)
I'm not sure which coordinate system would be the best, my ideas were:
1) 2D longitude-latitude - the simplest thing, there are simple and efficient algorithms to do that;
2) 2D in some other projection - partially solving the problem of unequal distances in 1), similarly, but there would need the projection to be done, a bit more of code
3) 3D using the real volume of the Earth - a bit more complicated, but I'm still sure efficient algorithms exist. There would be some coordinates transformation, but probably simpler than that of 2). This would have the great advantage of removing the singularity at W/E180 (e.g. doing Alaska+Siberia wouldn't generate much different score from Alaska+Canada with the same distances).
I understand you don't have these things in your engine, can you add it as an "external subroutine"? I would volunteer to implement it, if it uses some reasonable language...