Distance to $k$th nearest neighbor efficiently for arbitrary $k$
For a general metric, you can't.  For instance, one can prove it takes at least quadratic time to answer $\Theta(n)$ queries, in the worst case.
For instance, suppose we have $n/2$ query points that are all very far from each other, and $n/2$ target points.  We'll ask for the $n/4$-th closest neighbor of each query point.  Then each $d(q,t)$ can be set to any distance in $[1/2,1]$ for each of the $n^2/4$ pairs of a query point $q$ and a target point $t$, and each can be chosen independently, and you'll have a valid metric.  Thus you can imagine the distance being specified by a $n/2 \times n/2$ matrix of distances $d(q,t)$.  In $o(n^2)$ time, you can only read $o(n^2)$ of the entries in that matrix, which isn't sufficient to answer all of the queries.  You can prove this with an adversarial argument: consider any $q$ where the algorithm has read $d(q,t)$ for fewer than $n/4$ different values of $t$; then whatever the algorithm outputs as the $n/4$-th nearest neighbor to $q$, we can arrange the other unread distances so that the algorithm's output was incorrect.