Lower bound of degree of polynomial approximating parity
You can show a polynomial of degree $O(\sqrt{n\log n})$ can agree with parity on all but $o(1)$ fraction of the inputs. (In fact, this argument should work for anything of degree $\omega(\sqrt{n})$). 

Let $S = x_1 + x_2 + \dots + x_n$. Note that $\text{MOD}_2(x_1, x_2, \dots, x_n)$ can be written as a single-variable function of $S$. By Lagrange interpolation, there exists a univariate polynomial of degree $O(\sqrt{n\log n})$ in $S$ (and hence in the $x_i$s) that agrees with $\text{MOD}_2$ on the interval $S \in [(n-\sqrt{n\log n})/2, (n+\sqrt{n\log n})/2]$. By the central limit theorem, this range of $S$ accounts for all but $o(1)$ of the $2^n$ inputs $(x_1, x_2, \dots, x_n)$.