SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?
We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end.

You might be interested in Lee Raghavendra Steurer '14. They seem to be saying there can be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c &lt; 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there are instances of Max-CUT requiring higher degree. I lack the expertise to be sure I'm interpreting this correctly though.

Other than this, I don't know of any lower bounds for the degree of SOS that can solve Max-CUT exactly.