I'm partial to Milnor's proof in Topology from the Differentiable Viewpoint, a slightly simpler variant of the "every complex non-constant polynomial $p$ is surjective" proof given above, published somewhat earlier (1965). In brief:
Definition: Let $f: M \to N$, $M,N \subset \mathbb{R}^n$, $M$ compact, then, for each regular value $y \in N$, $$\#f^{-1}(y) = \text{number of points in the inverse image of $y$}.$$
Lemma: $\#f^{-1}$ is locally constant on the set of regular values.
Proof of lemma: Since $f$ is a diffeomorphism in a neighborhood of each $x_i \in f^{-1}(y)$, we can choose pairwise disjoint neighborhoods $U_i$ for the $x_i$, let $V_i = f(U_i)$, and then $$\#f^{-1}(V_1 \cap \cdots \cap V_k - f(M - U_1 - \cdots - U_k)) = \{\#f^{-1}(y)\}.$$
Proof of the F.T.A.: Using stereographic projection, we can consider the polynomial as a smooth map $f: S^2 \to S^2$. Since $f$ has only a finite number of critical points, the set of regular values is connected; the locally constant $\#f^{-1}$ is therefore constant on this set. As $\#f^{-1}$ cannot be zero for all regular values of $f$, it must be zero for none. Thus $f$ is surjective, and the polynomial has a root.
