Using Haversine distance increases it to only 13ms. I'm not sure why your Python implementation is so slow? In the real world, things like haversine are implemented as C extensions, so I wrote one for Ruby as a comparison and it runs in 3.8ms for 16k points. https://gist.github.com/jamatthews/d910a2b39c87a871264dd31d1...

The Ruby GIS libaries already have C implementations for haversine but I just wanted to show how easy it is to hook out to a C function for math heavy stuff.