dipende da quanto vuoi killare il server

http://mathworld.wolfram.com/GreatCircle.html

Con la formula (5) calcoli una distanza (in linea d'aria) abbastanza corretta - anche con il raggio terrestre approssimato (visto che varia tra i 6356 e i 6378 km), visto che della terra si può dire tutto, fuorché che sia una sfera... però non so quanto bene possa fare nel caso degli 8000 (o quanti sono) comuni italiani...

Qualcosa di più efficiente, anche se molto meno preciso, potrebbe essere lo "spalmare" l'italia sul piano e andarci di teorema di pitagora