Comparing the growth of $f\circ g$ and $g\circ f$

Suppose that $g$ satisfies $g(x)>x$ for all $x$, and also that $f$ and $g$ lie in a Hardy field, as suggested by Todd Trimble. (A Hardy Field, called an order of infinity by Hardy is a collection of germs of differentiable functions at $\infty$ that is closed under differentiation and composition, as well as the field operations. In particular, this means that for any Hardy field, $H$, and any $f\ne g\in H$, $f-g\in H\setminus\{0\}$, so that $1/(f-g)\in H$. In particular, $f-g$ is eventually positive, or eventually negative. That is, there is a total ordering on a Hardy field.)

Then I believe there is an extension Hardy field containing $f$, $g$ and a function, $h$ satisfying $h(g(x))=h(x)+1$. That is, $h(x)$ counts how many times you have to apply $g$ to 0 to get to $x$ (think of $\log^* x$).

Assuming the existence of such a Hardy field, there is now an affirmative answer to your question. If you conjugate $g$ by $h$, you obtain $\tilde g:=h\circ g\circ h^{-1}$ is $\tilde g(x)=x+1$. Conjugating $f$ by $h$ also to obtain $\tilde f$, your question is equivalent to asking whether $\tilde f(\tilde g(x))>\tilde g(\tilde f(x))$. That is, whether $\tilde f(x+1)>\tilde f(x)+1$. Notice that both $\tilde f$ and $\tilde g$ belong to the Hardy field.

The condition that $f>g^n$ for all $n$ means that $\tilde f(x)>x+n$ for large $x$, that is $\tilde f(x)-x\to\infty$. In a Hardy field, any function satisfying this satisfies $\tilde f'(x)>1$ for all large $x$. By the mean value theorem, this implies that $\tilde f(x+1)>\tilde f(x)+1$, as required.