I know how to calculate a least-squares regression, which minimizes the sum of the squares of the distances to the line.

Instead, I want to minimize the the maximum distance (of any point) to the line.

Can someone point me in the right direction .... is there a formula or would it be some kind of iterative refinement?

You need more fit coefficients, that is, a higher order fit. First order (linear) being y = mx +b, now you are talking about a polynomial fit curve with higher order like y = ax^3 + bx^2 + cx +d.

For a perfect fit you need n-1 orders, that is to fit to 4 points exactly requires a 3rd order polynomial fit curve. My apologies if I have missed your point or have oversimplified.