Proof that every polynomial of odd degree has one real root
Method of FTA: $$P(\overline z)=\sum_{k=0}^{2n+1}a_k\overline z^k=\sum_{k=0}^{2n+1}\overline a_k\overline{z^k}=\sum_{k=0}^{2n+1}\overline{a_kz^k}=\overline{\sum_{k=0}^{2n+1}a_kz^k}=\overline{P(z)}$$ which states $z$ is a root for $P(z)=0$ iff its complex conjugate $\bar z$ is. According to FTA, there are odd number of roots for a polynomial of odd degree. That implies there must be one single root $z$ satisfying $z=\bar z$, hence the real root.
Method of IVT:
$$\frac{P(x)}{x^{2n+1}}=1+\sum_{k=0}^{2n}a_k\frac{x^k}{x^{2n+1}}=1+\sum_{k=0}^{2n}a_kx^{k-(2n+1)}$$ For any $\varepsilon>0$, there exists $N>0$ such that for all $|x|>N$, $\left|\sum_{k=0}^{2n}a_kx^{k-(2n+1)}\right|<\varepsilon$. Hence for $x>N$, we have $P(x)>x^{2n+1}-\varepsilon x^{2n+1}>0$ and similarly for $x<-N$, we have $P(x)<0$. Then IVT implies there exists some $y$ such that $P(y)=0$.
Indeed it is true that all proofs of the fundamental theorem of algebra need some piece of analysis. Even the most algebraic proof of FTA (Euler, Gauß II) relies on the fact that all odd-degree real polynomials have at least one real root.
First consider the case of relatively large positive $x$. Assuming $x\ge 1$ as provisional lower bound, then $1\le x^k\le x^{2n}$ for $0\le k\le 2n$ and the value of the polynomial is bounded below by $$ P(x)\ge x^{2n+1}-\sum_{k=0}^{2n}|a_k|x^k\ge x^{2n+1}-x^{2n}\sum_{k=0}^{2n}|a_k| =x^{2n}\left(x-\sum_{k=0}^{2n}|a_k|\right) $$
We can now try to push the last expression on the right into positive territory by increasing the lower bound for $x$. At the Lagrange root bound $$ R=\max\left(1,\sum_{k=0}^{2n}|a_k|\right), $$ the right side for $x\ge R$ gives a non-negative bound. Increasing the lower bound to $x\ge 2R$ will result in $$ x≥2R \implies P(x)\ge (2R)^{2n}\cdot R\ge 2^{2n}>0. $$
The same reasoning can be applied to $-P(-x)=x^{2n+1}-a_{2n}x^{2n}+a_{2n-1}x^{2n-1}\mp...-a_0$, so that
$$x≤-2R \implies P(x)≤-(2R)^{2n}\cdot R≤-2^{2n}<0.$$
In total one obtains $$ P(-2R)≤-(2R)^{2n}\cdot R ≤ -2^{2n}<0<2^{2n}≤(2R)^{2n}\cdot R≤P(2R) $$ which allows to apply the intermediate value theorem for $P$ concluding for a real root of $P$ inside $(-2R, 2R)$, but really already inside $(-R,R)$.
Let $p(x)=a_0 + a_1 x + \dots + a_n x^n$ a polynomial $p: \mathbb{R} \to \mathbb{R}$ with $n$ odd and $a_n \neq 0$. Suppose $a_n >0$. We can write $p(x) = a_n x^n \cdot r(x)$ with $$r(x) = \frac{a_0}{a_n} \cdot \frac{1}{x^n} + \frac{a_1}{a_n} \cdot \frac{1}{x^{n-1}}+ \cdots + \frac{a_{n-1}}{a_n} \cdot \frac{1}{x} + 1.$$
So, we have $$\lim_{x \to +\infty} r(x) = \lim_{x \to -\infty} = 1.$$ Thus $$\lim_{x \to +\infty} p(x) = \lim_{x \to +\infty} a_n x^n = +\infty$$ and $$\lim_{x \to -\infty} p(x) = \lim_{x \to -\infty} a_n x^n = -\infty$$ because $n$ is odd. Therefore the interval $p(\mathbb{R})$ is ilimited inferior and superiorly, i.e. $p(\mathbb{R}) = \mathbb{R}$. This means that $p: \mathbb{R} \to \mathbb{R}$ is sujective. In particular, there is $c \in \mathbb{R}$ that $p(c)=0$.
For a polynomial with even degree, take $p(x)=x^2+1$. This have not real roots.