In general, does $f(g)$ and $f(h)$ have the same time complexity?
No, $f \circ g$ and $f \circ h$ (to use the standard mathematical notation) do not in general have the same complexity. For example, take $g(x) = 1$ (constant function) and $h(x) = x$ (identity function). Then $(f \circ g)(x) = f(1)$ and $(f \circ h)(x) = f(x)$; these functions only have the same complexity if $f = \Theta(1)$ (i.e. $f$ is asymptotically constant). This shows that the only functions $f$ for which all functions of the form $f \circ g$ have the same complexity are the ones that are asymptotically constant.

With the example $f = \lg^*$, growth is very slow, so a lot of functions “collapse” when you plug them into $\lg^*$. Nonetheless it is easy to cancel this collapse: define the function $e(y) = \min\{x \mid \lg^*(x) \ge y\}$. This is essentially an inverse function for $\lg^*$ (growing by $1$ at increasingly long intervals). With this you can easily construct functions that grow at any rate you like: $f(e(x)) \approx x$, $f(e(x^2)) \approx x^2$, etc.

(N.B. In my mathematical statements, I assume functions from $\mathbb{N}$ to $(0,\infty)$.)