The sequence $F_{\alpha}(n)$ indeed does not depend on $\alpha$ when $\alpha \geq \omega$. This question is closely related to <a href="http://mathoverflow.net/questions/103486">this other question</a>, and I will refer to my answer in that question.

Let $S_\alpha(n)$ be the set of ordinals defined by $\alpha ^ {\alpha ^ {\cdots ^ \alpha}}$ with all possible arrangements of parentheses.  Since $\alpha = \alpha^{\alpha^0}$ and $(\alpha^{\alpha ^ \beta})^{\alpha^{\alpha^\gamma}} = \alpha^{\alpha ^ {\beta + \alpha^\gamma}}$, every element of $S_\alpha(n)$ is of the form $\alpha^{\alpha ^ \beta}$.  So we define $T_\alpha (n) = \{ \beta | \alpha^{\alpha^\beta} \in S_\alpha(n) \}$.  We observe that $T_\alpha(0) = \{ 0 \}$ and $T_\alpha(n) = \{ \beta + \alpha^\gamma | \beta \in T_\alpha(i), \gamma \in T_\alpha(j), i + j = n - 1 \}$.

From my answer to the other question, we observe that $T_\alpha(n)$ is contained in the set $E(\alpha)$, which I refer to as the "exponential polynomials over the base $\alpha$".  For each element $\beta$ of $E(\alpha)$, we can write $\beta$ in the iterative normal form to the base $\alpha$, which I describe as follows:

0 is represented as 0

$\beta$ is represented as $\alpha^{\beta_1} + \alpha^{\beta_2} + \ldots + \alpha^{\beta_n}$, where $\beta_1 \geq \beta_2 \geq \ldots \geq \beta_n$ and each $\beta_i$ is itself represented in iterative normal form.

We claim that, for any n and any $\alpha, \beta \geq \omega$, $T_\alpha(n)$, when written in iterative normal form, is the same set as $T_\beta(n)$, except the base $\beta$ is replaced everywhere it appears by $\alpha$.  If we let $f(\gamma)$ be the ordinal obtained by replacing the base $\beta$ by $\alpha$ everywhere in the iterative normal form of $\gamma$, our claim amounts to $T_{\alpha}(n) = f(T_\beta(n))$.  From our above expression for $T_\alpha(n)$, we see that it suffices to show that $f(\gamma + \beta^\delta) = f(\gamma) + \alpha^{f(\delta)}$ for any $\gamma, \delta \in E(\beta)$.

Let $\gamma = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_n}$.  Let $m$ be the largest index such that $\gamma_m \geq \delta$.  Then we claim that

$\gamma + \beta^\delta = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_m} + \beta^\delta$

(note that this is in iterative normal form, provided that $\gamma_i$ and $\delta$ are.)

First we prove:

Lemma.  If $\beta, \mu, \nu$ are any ordinals such that $\mu < \nu$, then $\beta^\mu + \beta^\nu = \beta^\nu$.

Proof:  Let $\beta = \omega^{\beta_1} + \omega^{\beta_2} + \ldots + \omega^{\beta_n}$ be the Cantor Normal Form for $\beta$.  Then the leading term of the Cantor Normal Form of $\beta^\mu$ will be $\omega^{\beta_1 \mu}$, i.e.

$\beta^\mu = \omega^{\xi_1} + \omega^{\xi_2} + \ldots + \omega^{\xi_m}$ where $\xi_i \leq \beta_1 \mu$.

Since $\omega$ is a principal ordinal, for $\mu < \nu, \omega^\mu + \omega^\nu = \omega^\nu$.  Therefore

$\beta^\mu + \beta^\nu = \omega^{\xi_1} + \omega^{\xi_2} + \ldots + \omega^{\xi_m} + \beta^\nu = \beta^\nu$, as desired.  (end of proof of Lemma)

Therefore, since $\gamma_i \leq \delta$ for $m+1 \leq i \leq n$, we have

$\beta^{\gamma_{m+1}} + \ldots + \beta^{\gamma_n} + \beta^\delta = \beta^\delta$

and therefore

$\gamma + \beta^\delta = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_m} + \beta^\delta$.

We have

$f(\gamma) = \alpha^{f(\gamma_1)} + \alpha^{f(\gamma_2)} + \ldots + \alpha^{f(\gamma_n)}$

$f(\gamma + \beta^\delta) = \alpha^{f(\gamma_1)} + \alpha^{f(\gamma_2)} + \ldots + \alpha^{f(\gamma_m)} + \alpha^{f(\delta)}$,

and, provided that $m$ is the largest index such that $f(\gamma_m) \geq f(\delta)$, the same argument as above shows that

$f(\gamma) + \alpha^{f(\delta)} = \alpha^{f(\gamma_1)} + \alpha^{f(\gamma_2)} + \ldots + \alpha^{f(\gamma_n)} + \alpha^{f(\delta)} $ $= \alpha^{f(\gamma_1)} + \alpha^{f(\gamma_2)} + \ldots + \alpha^{f(\gamma_m)} + \alpha^{f(\delta)} = f(\gamma + \beta^\delta)$.

So we are done if we can show that for all $\gamma, \delta \in E(\beta)$, $\gamma < \delta \Leftrightarrow f(\gamma) < f(\delta)$.

This follows from the fact that we can describe the comparison relation < using the same inductive rules, regardless of base.  The inductive rules are as follows:

0 is less than any ordinal besides 0.

If $\gamma = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_m}$, and $\delta = \beta^{\delta_1} + \beta^{\delta_2} + \ldots + \beta^{\delta_n}$, with the $\gamma_i$ and the $\delta_i$ weakly decreasing, than $\gamma < \delta$ if and only if one of the following two conditions hold:

1. For some $i$, $\gamma_i < \delta_i$ and for all $1 \leq j < i, \gamma_j = \delta_j$.

2. $m < n$ and for all $1 \leq i \leq m$, $\gamma_i = \delta_i$.

It is easy to see that if the second condition holds, then $\gamma < \delta$.  So assume the  first condition holds.  Since $\beta \geq \omega$ and $\delta_i \geq \gamma_i + 1$,

$\beta^{\delta_i} \geq \beta^{\gamma_i + 1} \geq \beta^{\gamma_i} \omega > \beta^{\gamma_i} m \geq \beta^{\gamma_i} + \beta^{\gamma_{i+1}} + \ldots + \beta^{\gamma_m}$, so

$\beta^{\delta_1} + \beta^{\delta_2} + \ldots + \beta^{\delta_n} \geq \beta{\delta_1} + \beta^{\delta_2} + \ldots + \beta^{\delta_i} = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_{i-1}} + \beta^{\delta_i} > \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_{m}}$.

Going the other way, observe that, if neither conditions 1 nor 2 hold for $\gamma < \delta$, nor conditions 1 nor 2 hold for $\delta < \gamma$, we must have $m = n$ and $\gamma_i = \delta_i$ for $1 \leq i \leq m$, so $\gamma = \delta$.  So if $\gamma < \delta$, either conditions 1 or 2 must hold.

We have shown that $T_\alpha(n)$ and $T_\beta(n)$ are the same ordinals except for a change of base from $\alpha$ to $\beta$.  It follows that $S_\alpha(n)$ and $S_\beta(n)$ are the same except for the same change of base.  So $F_\alpha(n) = F_\beta(n)$ for any $\alpha, \beta \geq \omega$.

----------------------------------------------------------------------------------------

As for the asymptotics of $F_\omega(n)$, all I can prove is that $F_\omega(n) \geq 2^{n-2}$.  Take any binary string of n-2 symbols.  Starting from $\omega^\omega$, apply the function $\alpha \rightarrow \alpha^\omega$ if the $i$th symbol is a 0, and apply the function $\alpha \rightarrow \omega^\alpha$ if the $i$th symbol is a 1.  Defining $\beta$ by $\alpha = \omega^{\omega^\beta}$, the two operations affect $\beta$ by $\beta \rightarrow \beta + 1$ and $\beta \rightarrow \omega^\beta$ respectively.  It's not hard to see that two distinct binary strings lead to two different final ordinals.

I conjecture that $\lim_{n \rightarrow \infty} \frac{F_\omega(n+1)}{F_\omega(n)} = 4$, but am nowhere close to a proof.