I assume you are aware of the classic paper by Jon Bentley, "Multidimensional divide-and-conquer" [Commun. ACM 23(4):214-229 (1980)], in which he showed how to find the closest pair of points in $\mathbb{R}^3$ in the Euclidean metric in $O(n \log n)$ time. His algorithm works in arbitrary dimensions, with the constant dependent on $d$. I realize I am not answering your question about metric spaces, but it might be worth revisiting his algorithm to see how heavily it leans on the norm.

Rabin's 1976 randomized algorithm achieves $O(n)$ expected time. An updated detailed analysis is in the paper "A Reliable Randomized Algorithm for the Closest-Pair Problem" by Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen [Journal of Algorithms 25(1): 19-51 (1997)]. Again I am not addressing your focus on other metric spaces, but these efficient algorithms for Euclidean distance would be a place to start.

I assume you are aware of the classic paper by Jon Bentley, "Multidimensional divide-and-conquer" [Commun. ACM 23(4):214-229 (1980)], in which he showed how to find the closest pair of points in $\mathbb{R}^3$ in the Euclidean metric in $O(n \log n)$ time. His algorithm works in arbitrary dimensions in $O(n \log^{d-1} n)$. I realize I am not answering your question about metric spaces, but it might be worth revisiting his algorithm to see how heavily it leans on the norm.

Rabin's 1976 randomized algorithm achieves $O(n)$ expected time. An updated detailed analysis is in the paper "A Reliable Randomized Algorithm for the Closest-Pair Problem" by Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen [Journal of Algorithms 25(1): 19-51 (1997)]. Again I am not addressing your focus on other metric spaces, but these efficient algorithms for Euclidean distance would be a place to start.