In $\mathbb{R}^3$, given a set of lines $S$, find a line $L$ that minimizes $$ \sum_{s_i \in S} D( L, s_i ) $$ where $D( \cdot , \cdot )$ is the Euclidean distance between two lines (defined as the distance between their closest points).
I would also be happy to have an answer minimizing other metrics, like the sum of squared distances, the median distance, or the maximum distance.
Depending on the set of lines, this is a non-convex energy minimization problem.
There still might be a practical algorithm for finding a solution. One way to re-write this problem is as a minimization of closest distances:
$$ \min_{\mathbf{q},\mathbf{v}} \sum_{i=1}^n \left( \min_{t_i} \left\| (\mathbf{q}+t_i\mathbf{v}-\mathbf{p}_i)- ((\mathbf{q}+t_i\mathbf{v}-\mathbf{p}_i)\cdot\mathbf{u}_i)\mathbf{u}_i \right\|^2 \right) $$ where $\mathbf{q}$ and $\mathbf{v}$ are a point and the direction vector of your line $L$ and $\mathbf{p}_i$ and $\mathbf{u}_i$ are a point and the direction vector on the $i$th line $s_i$ in your set of lines $S$.
This is very similar in form to the typical form minimized by the iterative closest point (ICP) algorithm.
In this case, a minimal algorithm would proceed by repeatedly:
The optimal $\mathbf{q},\mathbf{v}$ are found with a linear system solve involving all lines in $S$, while each optimal $t_i$ can be found in parallel.
This optimization probably benefits from all the usual tricks for ICP like stochastic gradient descent, Gauss Newton (a.k.a., point-to-plane in ICP), and perhaps Alternating Direction Method of Multipliers (ADMM).