Fast approximate middle of points in a metric space?
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.