Finding non-trivial NFA that accepts all short strings
Your question is very similar to a similar question about regular expressions. My answer there (citing a paper of Jeff Shallit and his students) gives an example in which the minimal word not accepted has length exponential in the number of states (using the fact that a regular expression of length $\ell$ can be converted an NFA of length $O(\ell)$). Moreover, the NFAs are over a fixed alphabet.