Version 2
Here is some experimental evidence. Like most people here I'm using $-f(x)$ and assuming $0<b<a<1$.
Consider $b=1/100$ and $a=i/100$.
For $2\le i\le 3$, there is a quadratic polynomial.
For $4\le i\le 8$, the least degree is 3.
For $9\le i\le 15$, the least degree is 4.
For $16\le i\le 24$, the least degree is 5.
For $24\le i\le 35$, the least degree is 6. - corrected as per Peter K
For $36\le i\le 48$, the least degree is 7.
For $49\le i\le 63$, the least degree is 8.
For $64\le i\le 80$, the least degree is 9.
For $81\le i\le 99$, the least degree is 10.
Turbo noticed that these cutoffs are close to squares.
Next consider $a=1-\frac1n$, $b=\frac1n$. We find:
For $3\le n\le 4$, there is a quadratic poynomial.
For $5\le n\le 9$, the least degree is 3.
For $10\le n\le 16$, the least degree is 4.
For $17\le n\le 25$, the least degree is 5.
For $26\le n\le 36$, the least degree is 6.
For $37\le n\le 49$, the least degree is 7.
For $50\le n\le 64$, the least degree is 8.
For $65\le n\le 81$, the least degree is 9.
For $82\le n\le 100$, the least degree is 10.
For $101\le n\le 121$, the least degree is 11.
For $122\le n\le 144$, the least degree is 12.
Turbo's square-root conjecture is looking pretty good, and I see PeterKravchuk has proved it. The solutions look very much like scaled-and-shifted Chebyshev polynomials inside the box and surely that is the place to look for an analytic upper bound on the degree.
Here is my method. We are looking for $c_1,\ldots,c_d$ such that $f(x)=c_1x+\cdots +c_dx^d$ has the desired properties. Let $X$ be some finite subset of $[b^2,a^2]$ including the two endpoints. Initially I take $X$ to consist of $2d+1$ points uniformly spaced.
Make a linear program whose variables are $m,c_1,\ldots,c_d$ and whose constraints are $f(x)\in[b+m,a-m]$ for $x\in X$ and $m\ge 0$. Maximize $m$. If the constraints are infeasible, we have proved that no good polynomial of degree at most $d$ exists. If there is a solution, let $f(x)$ be that polynomial. Check if $f(x)$ is good by finding its turning points and evaluating $f(x)$ there. (Alternatively, use Sturm sequences to prove this in rational arithmetic.) If $f(x)$ is good, we are done; if not, add (an accurate rational approximation of) the turning points of $f(x)$ to $X$ and repeat.
This method won't work if there are only solutions which hit the bounds exactly, but I didn't find any other case when it doesn't work. Usually only 2 or 3 iterations are needed.
Maple worksheets: version 16, older version (not tested).