Is there some constant $c > 0$ such that, for all large enough $n$ and all polynomials $P$ of degree $n$ with coefficients in $\{-1, 1\}$, $$\max_{|z|=1} |P(z)| > (1 + c) \sqrt{n}?$$

The trivial lower bound from Parseval's identity: for any polynomial $P$ of degree $n$ with coefficients in $\{-1, 1\}$, we have $\max_{|z|=1} |P(z)| \geq \sqrt{n+1}$.

This follows from Parseval's identity: $$\frac{1}{2\pi} \int_0^{2\pi} |P(e^{i\theta})|^2 d\theta = \sum_{k=0}^{n} |a_k|^2 = n+1$$ since each $|a_k|^2 = 1$.