I think it is easier to think about the question generalized to an arbitrary transitive model  of ZFC, resisting the natural urge to grasp towards the Absolute. So fix such a model $M$, and let $\mathcal T^M(\alpha)$, $F^M$, and $S^M(\alpha)$ be as you defined them, replacing $V$ with $M$. Let's omit the superscripts, though.

The ordertype of $F$ is a limit ordinal: if $\alpha$ is fresh, so is $\alpha+1$, since in general, one can recover $\mathcal T(\beta)$ from $\mathcal T(\beta+1)$. 

Note that if $\alpha$ is definable in $M$, $\mathcal T(\alpha)$ is fresh since it is the unique value of the function $\mathcal T$ containing the index of the formula $\varphi(\text{dom}(x))$ where $\varphi$ defines $\alpha$. In particular, an ordinal that is not fresh is not definable, and so your least stale ordinal is not definable.

Note that if every ordinal of $M$ is definable in $M$, then every ordinal is fresh. More interestingly, even models with undefinable ordinals can have only fresh ordinals. (I think Con(ZFC) does not suffice to build a model of ZFC whose fresh ordinals form a set.) To avoid these examples, assume from now on that $(M,S)$ satisfies the Axiom of Replacement where $S$ is the satisfaction predicate of $M$. 

The fresh ordinals $F$ then form a set in $M$. Moreover, $(\mathcal T(\alpha))_{\alpha \in F}$ is definable in $M$ from any sufficiently large ordinal $\kappa$ such that $V_\kappa^M\prec M$ (and there are cofinally many). It follows that $(\mathcal T(\alpha))_{\alpha \in F}$ belongs to $\text{HOD}^M$, which I will denote by $H$. Therefore $F$, has cardinality at most $\mathfrak c$ in $H$. For any ordinal $\alpha < \mathfrak{c}^H$, the $\alpha$-th real in the canonical wellorder of $H$ is $\Sigma_2$-definable from $\alpha$ and hence is recoverable from $\mathcal T(\alpha)$. It follows that $\alpha$ is fresh. This shows $\mathfrak{c}^H\subseteq F$. Also $\mathfrak{c}^H\in F$, being definable in $M$. So the ordertype of $F$ is strictly between $\mathfrak{c}^H$ and $\mathfrak{c}^{+H}$.

Now it is clear that $F$ is uncountable if and only if $M$ thinks $H$ contains uncountably many ordinal definable reals, which of course depends on the choice of $M$. The cardinality of $F$ is larger than $\aleph_1$ if and only if $H$ contains at least $\aleph_2$-many reals, which is independent of $\neg\text{CH}$. 

Assuming Martin's Maximum, every subset of $\omega$ is coded into the pattern of stationary reflection for any infinite stationary partition of $\{\alpha < \kappa : \text{cf}(\alpha) = \omega\}$ where $\kappa\geq \omega_2$. (This is part of the proof of Theorem 10 in Foreman-Magidor-Shelah's [Martin's Maximum, saturated ideals, and nonregular ultrafilters][1].) So assuming $M$ satisfies MM, large cardinals, and Woodin's HOD Hypothesis, every real is in $H$. Therefore it is conceivable that your question decided by the conjunction of forcing axioms and large cardinals, but this is open...

For the second question, note that by the pigeonhole principle there is an unbounded class $C\subseteq M$ of ordinals such that for all $\kappa_0,\kappa_1\in C$, the theory of $\kappa_0$ in $(M,S)$ with real parameters is the same as that of $\kappa_1$. Let $\langle-,-\rangle$ be an $M$-definable pairing function. It follows that $\mathcal T\langle\kappa_0,\alpha\rangle$ is equal to $\mathcal T\langle\kappa_1,\alpha\rangle$ for all $\alpha < \mathfrak{c}^H$, since $\alpha$ is interdefinable over $M$ with the $\alpha$-th real in the canonical wellorder of $H$
and  $\mathcal T\langle\kappa_0,\alpha\rangle$ depends only on the theory of $\kappa_0$ and $\alpha$ in $(M,S)$. But similarly, for each $\kappa\in C$, the $\mathcal T\langle\kappa,\alpha\rangle$ are distinct for $\alpha < \mathfrak{c}^{H}$; let $\xi_{\alpha}$ be the least ordinal $\xi$ such that $\mathcal T(\xi) = \mathcal T\langle\kappa,\alpha\rangle$. 
Letting $E\subseteq F$ be the set of ordinals $\alpha$ such that $S(\alpha)$ a proper class in $M$, it follows that $\{\xi_\alpha : \alpha < \mathfrak{c}^{H}\}\subseteq E$, so $E$ has cardinality $\mathfrak{c}$ in $H$. So much of what was said above applies to $E$ as well.


  [1]: https://www.jstor.org/stable/1971415