The desired polynomials with $ a_0 = -1 $ are the negatives of those with $ a_0 = 1, $ so consider $ a_0 = 1 $. By Vieta's formulas, $ -a_1 $ is the sum of all the zeros, and $ a_2 $ is the sum of all possible pairwise products. Therefore, the sum of the squares of the zeros of $ x^n + a_1 x^{n-1} + \dots + a_n $ is $ a_1^2 - 2a_2 $. The product of the square of these zeros is $ a_n^2 $. Let the roots be $ r_1 $, $ r_2 $, $ \dots $, $ r_n $, so \[r_1^2 + r_2^2 + \dots + r_n^2 = a_1^2 - 2a_2\]and $ r_1^2 r_2^2 \dotsm r_n^2 = a_n^2 $. If all the zeros are real, then we can apply AM-GM to $ r_1^2 $, $ r_2^2 $, $ \dots $, $ r_n^2 $ (which are all non-negative), to get $$\frac{a_1^2 - 2a_2}{n} \geq (a_n^2)^{1/n},$$with equality only if the zeros are numerically equal. We know that $ a_i = \pm 1 $ for all $ i $, so the right-hand side is equal to 1. Also, $ a_1^2 = 1 $, so for the inequality to hold, $ a_2 $ must be equal to $ -1 $. Hence, the inequality becomes $ 3/n \ge 1 $, so $ n \le 3 $. Now, we need to find an example of such a 3rd-order polynomial. The polynomial $ x^3 - x^2 - x + 1 $ has the given form, and it factors as $ (x - 1)^2 (x + 1) $, so all of its roots are real. Hence, the maximum degree is $ \boxed{3} $.