Smallest representatives of a quotient by an equivalence relation
It seems to me that your question is too general to answer.  Let me focus on the case of ∼L.  Then here is an example which shows a lower bound; namely, the length of a representative can be at least $e^{(1-o(1))\sqrt{n \ln n}}$, where n is the number of states of the minimum DFA.

We will actually show a lower bound on the length of a representative with respect to the right-equivalence relation RL on strings defined as: x RL y if and only if for all strings u, ux∈L ⇔ uy∈L.  Because equivalence relation RL is coarser than ∼L, any complete set of representatives with respect to ∼L must contain a complete set of representatives with respect to RL, and therefore a lower bound shown for RL applies also to ∼L.

Number-theoretic preparations.  Let pK be the Kth prime number.  We write the sum of the first K primes as Σ(K).  We also write the product of the primes that are less than or equal to N as N# (the primorial of N).  Then the following facts are known:


pK ∼ K ln K (from the prime number theorem).
Σ(K) ∼ K2 ln K (see the MathWorld article on prime sums).
ln(N#) ∼ N (see the MathWorld article on Chebyshev functions).


By combining these facts, we obtain that $\lim_{K\to\infty}\frac{\ln(p_K \#)}{\sqrt{\Sigma(K) \ln \Sigma(K)}} = 1$, and therefore $p_K \# = e^{(1-o(1))\sqrt{\Sigma(K) \ln \Sigma(K)}}$.

(I think that this final statement is a standard fact in the number theory, but I do not know a good reference for it.  See a related discussion in comments to this post.)

Construction and analysis.  For k∈ℕ, construct a DFA Mk on the alphabet {0, 1} as follows.  Let K=2k.  First, there is a complete binary tree of depth k rooted at the initial state.  Label the K leaves of this binary tree as q1, …, qK.  At each qi, we add a cycle of length pi, labeling each edge of the cycle with both 0 and 1 (that is, once you reach state qi, only the length of the rest of the string matters).  Mark the K states q1, …, qK as accepting states.

If x RL y, then we have that |x|≡|y| (mod pi) for every i≤K by prepending the binary notation of i−1 and some string of an appropriate length to both x and y.  This means that any complete set of representatives with respect to the relation RL contains at least one string with length at least pK#−1.

The number of the states in DFA Mk is K−1+∑i=1K pi = Σ(K)+K−1.  If we denote this number as n, then n ∼ Σ(K), and the length of at least one representative must be at least $p_K \# - 1 = e^{(1-o(1))\sqrt{n \ln n}}$.