For large $n$ and fixed $\epsilon > 0$ there is a polynomial of degree $d = O_\epsilon(\sqrt{n})$ that uniformly approximates $x^n$ to within $\epsilon$ on all of $[-1,+1]$. The polynomial can be taken to be the truncated Čebyšev expansion of $x^n$, as the original proposer (OP) suggested. As $\epsilon \rightarrow 0$, the $O_\epsilon$ constant grows only as $(\log(\epsilon^{-1}))^{1/2}$; for example, $d = 2.576 \sqrt{n}$ suffices to get $\epsilon = .01$ if I computed correctly.
The OP wrote that truncating the Čebyšev expansion will give the correct $L^\infty$ distance to within a log factor. I don't see a priori why this should be, but fortunately the coefficients of the expansion of $x^n$ in Čebyšev polynomials turn out to be elementary and familiar enough to work with explicitly.
It will be convenient to define $T_k(x)$ for all $k \in \bf Z$ as the polynomial such that $T_k(\cos u) = \cos ku$. Then $T_{-k} = T_k$ is a polynomial of degree $|k|$ satisfying $|T_k(x)| \leq 1$ for all $x\in [-1,+1]$. Now the Čebyšev expansion of $x^n$ is simply
$$
x^n = \frac1{2^n} \sum_{m=0}^n {n \choose m} T_{2m-n}(x),
$$
which can be checked by writing $x = \cos u = \frac12(e^{iu}+e^{-iu})$ and $T_k(x) = \frac12(e^{iku}+e^{-iku})$. So the coefficients form a binomial distribution, and truncating at degree $d$ eliminates only the tail of the distribution past $d^2/n$ standard deviations. Since each $|T_{2m-n}(x)| \leq 1$, this tail also bounds the truncation error for all $x \in [-1,+1]$, and we conclude that this error can be brought below any positive $\epsilon$ by making $d$ a large enough multiple of $\sqrt{n}$, as claimed.
This might not be the optimal $L^\infty$ approximation (except for $d=n-1$, when its optimality is the result of Čebyšev that you quoted), but it's not too far, because it is the best $L^2$ approximation with respect to the Čebyšev measure $\pi^{-1} dx/ \sqrt{1-x^2}$, and the $L^\infty$ distance is at least as large as the $L^2$ distance. The $L^2$ distance can be computed from the sums of the squares of the coefficients in the tail.
Much the same technique should work for $(1-x^2)^n$; indeed I see that while I was writing this Andrew posted an answer for $(1-x^2)^n$ that looks very similar to what I did for $x^n$.