Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points
How about:

Build a weighted complete bipartite graph where the left vertex set is $S$, the right vertex set is $G$, and the weight of the edge between $s \in S$ and $g \in G$ is the 3-D Manhattan distance from $s$ to $g$.
Solve the assignment problem for this graph.

This finds the exact minimum. It does unfortunately take about $O(n^3)$ for a typical network flow algorithm, though.