If there are equal coefficients for $x^{2n-t}$ and $x^t$ for all $0 \le t \lt n$ then we have $n+1$ unknown coefficients so $n+1$ points suffice. Of course that is still $O(n).$
For the quadratic case $y=ax^2+bx+a$ we have $y(i)=bi.$
For $y=ax^4+bx^3+cx^2+bx+a$ we have $y(I)=2a+c$ and $y(0)=a.$
for $y=ax^6+bx^5+cx^4+dx^3+cx^2+bx+a$ it is enough to have $y$ at $i$ and at $\frac{\pm1+\sqrt{3}i}{2}$
This suggests a reduction from $n+1$ to $n$ points. This is not using the fact that the coefficients are integers.
For the case $2n=4$ there are values $u,v$ with $v^4+1=2(u^4+1)$, $v^3+v=2(u^3+u)$ but $v^2 \ne 2 u^2$ thus one could find $c$ along with a certain linear combination of $a,b$ but not $a$ or $b.$
A useful question might be "we have a polynomial of degree $2n$ with (symmetric) integer coefficients. How many function evaluations are needed to decide if the middle coeffcient is $0$ or not?