Are there non-constructive proofs of existence of "small" Turing machines / NFAs?
Only an extended comment with a trivial example; you can pick the one-element language:

$$L_k = \{ M \mid  \sigma(M) = \Sigma(k) \}$$

i.e. $L_k$ contains the first (in lexicographical order) busy beaver Turing machine of size $k$ (the Turing machine of size $k$ that attains the largest number of 1s on its tape after halting).

For every $k$ the language $L_k$ is regular ... but we have no idea on how to  build the small DFA that recognizes it (though it has only $\leq 2*k(\log k+2)$ states) :-)