Find a subset in constant many queries
If you don't know any bounds on the coefficients beforehand, then you cannot give them any bound without $d$ queries. Suppose you have made queries of $f(x)$ on $x=x_1,\ldots,x_{d-1}$, and claim that the coefficients of $f(x)$ are all at least $-b$. However, a different monic polynomial $f(x)-N(x-x_1)\cdots(x-x_{d-1})$ has the same evaluation on all the $d-1$ queries, and when $N$ is large enough the coefficient of $x^{d-1}$ in this polynomial must be smaller than $-b$, leading to a contradiction.