n-state DFA that requires n-2 steps to check equivalence
Consider the following DFA on the alphabet $\{0\}$:


The states are $q_1,\ldots,q_n$, with $q_1$ initial and $q_n$ final.
$\delta(q_i,0) = q_{i+1}$ for $i &lt; n$, and $\delta(q_n,0) = q_n$.


Consider the pair of states $q_1,q_2$. For $i &lt; n-2$, $\delta^*(q_1,0^i),\delta^*(q_2,0^i) \notin F$, whereas $\delta^*(q_1,0^{n-2}) = q_{n-1} \notin F$, $\delta^*(q_2,0^{n-2}) = q_n \in F$.