All polynomials satisfying the problem's conditions are:
(i) $f(x) = g(x)$
(ii) $f(x) = S(x+a) - a, g(x) = -S(x+a) - a$, where $a$ is any real number, and $S$ is any odd polynomial function (i.e. $S(x) = \sum a_i x^{2k+1}$).

It is easy to see that $f(x)$ and $g(x)$ have the same degree. Let $F(x) = f(f(x)) = \sum_{i=0}^{m} a_m x^{m-i}$,
$G(x) = g(g(x)) = \sum_{i=0}^{m} b_m x^{m-i}$. Then the polynomials $F(x), G(x)$ satisfy $F(F(x)) = G(G(x))$. Write $H(x) = F(F(x)) = G(G(x)) = \sum_{i=0}^{m^2} h_i x^{m^2-i}$, and we will examine $h_0, h_1, \dots, h_m$ in order.

Expanding $F(F(x))$:
$$F(F(x)) = a_0(a_0x^m + a_1x^{m-1} + \dots + a_m)^m + a_1(a_0x^m + \dots + a_m)^{m-1} + \dots$$
Note that only the term $a_0(a_0x^m + a_1x^{m-1} + \dots + a_m)^m$ has degree in $x$ exceeding $m(m-1)$, so when computing $h_0, h_1, \dots, h_{m-1}$, we only need to look at this term.

First, from
$$h_0 = a_0^{m+1} = b_0^{m+1}$$
we can deduce that $a_0 = b_0$ or $a_0 = -b_0$, and the latter can only happen when $m$ is odd. For convenience of notation, we write $a_0 = sb_0$, where $s = 1$ or $-1$.

Next we use mathematical induction to prove that $a_i = sb_i, \forall 0 \le i < m$. The base case $i = 0$ has already been proven.
Suppose for some positive integer $k < m$, $a_i = sb_i$ holds for all $0 \le i < k$, then observe the equation
$$h_k = a_0 \sum_{r_1+\cdots+r_m=k} a_{r_1} a_{r_2} \cdots a_{r_m} = b_0 \sum_{r_1+\cdots+r_m=k} b_{r_1} b_{r_2} \cdots b_{r_m}$$
Among the terms in the $\Sigma$, if a term has every $r_i$ less than $k$, then every $r_i$ satisfies $a_{r_i} = sb_{r_i}$, and thus
$$a_0 a_{r_1} a_{r_2} \cdots a_{r_m} = s^{m+1} b_0 b_{r_1} b_{r_2} \cdots b_{r_m} = b_0 b_{r_1} b_{r_2} \cdots b_{r_m}$$
Therefore this term cancels out on both sides of the equation. The only remaining terms that cannot be cancelled are those where for some $i$, $r_i = k$ and all others are $0$. There are $m$ such terms in total, so
$$ma_0^m a_k = mb_0^m b_k = ms^m a_0^m b_k$$
so $a_k = sb_k$. By mathematical induction, we have proven $a_i = sb_i, \forall 0 \le i < m$.

It is worth mentioning that when $k = m$, $h_k$ will have one additional term beyond the above, namely $a_1 a_0^{m-1}$ and $b_1 b_0^{m-1} = s^m a_1 a_0^{m-1}$ (coming from the highest degree of the second largest term of $F(F(x))$). This means that when $s = 1$ we can still continue to deduce $a_m = sb_m$, giving one set of solutions $F(x) = G(x)$; but when $s = -1$ these extra two terms cannot cancel, so we cannot obtain information about the constant term, and we only get $F(x) = -G(x) + r$, where $r$ is some real number.

We continue the discussion for the case $F(x) = -G(x)+r$. Substituting this into $F(F(x)) = G(G(x))$ gives
$$G(G(x)) = F(F(x)) = -G(-G(x) + r) + r$$
Recall that in this case $m$ is odd, so $G(x)$ maps onto all real numbers, hence for any real number $a$ we can find $x$ such that $G(x) = \frac{r}{2} + a$, so
$$G(\frac{r}{2} + a) - \frac{r}{2} = -(G(\frac{r}{2} - a) - \frac{r}{2}), \forall a \in \mathbb{R}$$
This tells us that $G(x)$ is an odd function centered at $(\frac{r}{2}, \frac{r}{2})$.

At this point, we have deduced that if $F(F(x)) = G(G(x))$, then $F(x) = G(x)$, or $F(x) = S(x+a) - a, G(x) = -S(x+a) - a$, where $a$ is any real number, and $S(x)$ is any odd polynomial function. Substituting back to check, it is easy to see that both sets of solutions satisfy $F(F(x)) = G(G(x))$.

Returning to the original problem, let the degrees of $f(x)$ and $g(x)$ be $k$, with $k^2 = m$. If we are in the case $F(x) = S(x+a) - a, G(x) = -S(x+a) - a$, then $f(f(x)) = F(x)$ and $g(g(x)) = G(x)$ have leading coefficients differing by a sign.
But recall that in this case $m$ is odd, so $k$ is also odd, and then the leading coefficient of $f(f(x))$ will be $a_0^{k+1} > 0$, and similarly the leading coefficient of $g(g(x))$ is also greater than zero, a contradiction!

Therefore only the case $F(x) = G(x)$ remains, in which case $f(f(x)) = g(g(x))$, so we immediately know that all solutions satisfying the problem's conditions are:
(i) $f(x) = g(x)$