Consider the language $M_n = (L_n \#)^*L_n$, where $\#$ is a new symbol.
The NFA complexity of $M_n$ is $n$ (allowing for multiple initial states). Indeed, here is one NFA having $n$ states accepting $M_n$. The states are $q_1,\ldots,q_n$, all both initial and final. There is a self-loop around $q_i$ for each $j \neq i$. Furthermore, there are transitions from each $q_i$ to each $q_j$ labeled $\#$. The matching lower bound follows from the DFA complexity of $L_n = M_n \cap \{1,\ldots,n\}^*$ being $2^n$.
In contrast, we will show that the DFA covering complexity of $M_n$ is $2^n$. For the upper bound, consider a DFA whose states are $q_S$ for $S \subseteq \{1,\ldots,n\}$. The states keep track of the letters seen so far: the initial state is $q_\emptyset$, and $\delta(q_S,i) = q_{S \cup \{i\}}$. All states other than $q_{\{1,\ldots,n\}}$ are accepting. When seeing $\#$, if we're in $q_{\{1,\ldots,n\}}$ then we stay put, and otherwise we move to $q_\emptyset$.
Let $[n] = \{1,\ldots,n\}$. For $S \subseteq [n]$, let $w_S$ consist of all letters in $S$ in order. Let $P$ denote all words over $[n]$ containing each letter at most twice, and missing at least one letter.
Suppose that $M_n = \bigcup_{i=1}^N L(A_i)$, where the $A_i$ are DFAs. We can identify $L_i := L(A_i) \cap (P\#)^*P$ with a language over the alphabet $P$ in the natural way ($p_1\#\ldots\#p_\ell$ corresponds to the word of length $\ell$ whose letters are $p_1,\ldots,p_\ell$). Say that $x \in P^*$ is good for $L_i$ if for all $p \in P$ there exists $y_p \in P^*$ such that $xpy_p \in L_i$.
Suppose that no $x$ is good for $L_i$. Let $\ell \geq 0$. For $0 \leq r \leq \ell$, let $S_r$ be the set of length $r$ prefixes of words in $L_i \cap P^\ell$. If $|S_{r+1}| > (|P|-1)|S_r|$ for some $r < \ell$, then by the pigeonhole principle there is some $x \in S_r$ such that $xp \in S_{r+1}$ for all $p \in P$; but then $x$ is good. It follows that $|L_i \cap P^\ell| = |S_\ell| \leq (|P|-1)^\ell |S_0| = (|P|-1)^\ell$.
If no $x$ is good for any $A_i$, then for all $\ell \geq 0$ we have
$$
|P|^\ell \leq \sum_{i=1}^N |L_i \cap P^\ell| \leq N(|P|-1)^\ell,
$$
which is contradictory for large enough $\ell$. Therefore some $x$ is good for some $A_i$.
Let us identify $x \in P^*$ with the corresponding word over $[n] \cup \{\#\}$. Thus for each $p \in P$ there is $y_p \in M_n$ such that
$$
x\# p\# y_p \in L(A_i).
$$
We claim that the $2^n$ words $x \# w_S$ (we allow $S = [n]$) are pairwise inequivalent in the Myhill–Nerode relation of $L(A_i)$, and so $A_i$ has at least $2^n$ states.
Indeed, let $S,T$ be two different subsets of $[n]$. Assume without loss of generality that $j \in T \setminus S$. Since $w_S w_{[n] \setminus \{j\}} \in P$, by assumption $x \# w_S w_{[n] \setminus \{j\}} \# y_p \in L(A_i)$, where $p = w_S w_{[n] \setminus \{j\}}$. In contrast, $w_T w_{[n] \setminus \{j\}}$ contains all letters, hence $x \# w_T w_{[n] \setminus \{j\}} \# y_p \notin M_n$, and so $x \# w_T w_{[n] \setminus \{j\}} \# y_p \notin L(A_i)$. This shows that the two words $x \# w_S, x \# w_T$ are inequivalent.
