For n ~ 250k to 1.5M, I've use Manhattan distance (as opposed to Euclidean) in an analysis of neuroimaging functional data...but I am interested in people's takes on choosing a distance metric..There are so many exotics out there.