I don't think you can do euclidiean distance calculations like this. The distance associated with one degree of latitude changes as you move closer or further from the poles.
I believe you're correct. Terrestrial navigation usually uses non-euclidean spherical geometry so the haversine or great circle formulas would be more appropriate here. I've done similar analysis in the past and that's what I used.
