Fitting points to a polynomial, except by minimaxing instead of least squares

You can solve this minimax ($L_\infty$) polynomial regression problem via linear programming. See Curve Fitting: Fitting a Curve to a Set of Data Points, which demonstrates both $L_\infty$ and $L_1$.