Fast approximate middle of points in a metric space? Given $N$ points $X_i$ in a metric space
and a measure of "middleness"
$ \qquad \qquad \mathsf{middle}( X_i ) \equiv
\frac{1}{N} \sum_j \mathsf{metric}( X_i, X_j ) $
can one find an $X_i$ near the middle of all $N$ points,
i.e. roughly minimizing $\mathsf{middle}( X_i )$,
in time and space both better than $O( N^2 )$ ?
If not in general, are there cases that can be done &mdash; trees, Euclidean metrics ?  

Clarification: by "space better than $O(N^2)$" I mean,
are there approximate methods that give many nearby pairs 
after looking at $O(N^{1+\epsilon})$ of all pairs ?
This is broader than just middles.
Of course, guarantees are then gone, or empirical or statistical.
But methods that work for $N$ 10000 or 1000000 
would have broad application.
(Is that clear, is it worth a separate question ?)
There's a rather large literature on this problem. In brief, the problem you're looking at is called the $1$-median problem for a metric space. Since you're allowing for things "near" the middle, I'll assume approximations are ok. I also don't know what you mean by space less than $n^2$, since the input size itself is $n^2$. 

Having said that, for an arbitrary metric space you can get a "sublinear" approximation (i.e one that runs in $o(n^2)$ time. Specifically, Piotr Indyk showed that you can get a $(1+\epsilon)$ approximation in time linear in $n$ and polynomial in $1/\epsilon$. 

For structured spaces you can also do quite well. In Euclidean space, core-set techniques for the $k$-median problem (of which the 1-median is a special case) give you similar bounds (linear in n) to get arbitrarily good approximations. The caveat in this case is that the solution you get might not be one of the input points.