Consider the following optimization problem:

Problem: find a monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$.

The solution is given by Chebyshev polynomials:

Theorem: Let $T_n(x) = cos (n \cdot cos^{-1} x)$. Then $(1/2^{n-1}) T_n$ is a monic polynomial of degree $n$ which achieves the above minimum.

The proof of this fact is short and surprisingly free of messy calculations. From the definition of $T_n$ you derive a recurrence relation expressing $T_n$ in terms of $T_{n-1}, T_{n-2}$, which shows that $T_n$ are indeed polynomials. Then you argue that $(1/2^{n-1}) T_n$ is monic and achieves its extrema $\pm 1/2^{n-1}$ at least $n+1$ times in $[-1,1]$, from which the above theorem easily follows. If you'd like a nice exposition of this argument which does not skip any steps, this is short and clear.

However, I don't get much enlightenment from this proof: it feels pulled out of a hat. For example, it gives me no clue about which other polynomial optimization problems have similar solutions.

My question: Is there a natural and motivated sequence of steps which, starting from the above optimization problem, leads to Chebyshev polynomials?