  An $\epsilon$-distance-uniform graph is one in which from every vertex, all
but an $\epsilon$-fraction of the remaining vertices are at some fixed distance
$d$, called the critical distance. We consider the maximum possible value of
$d$ in an $\epsilon$-distance-uniform graph with $n$ vertices. We show that for
$\frac1n \le \epsilon \le \frac1{\log n}$, there exist
$\epsilon$-distance-uniform graphs with critical distance $2^{\Omega(\frac{\log
n}{\log \epsilon^{-1}})}$, disproving a conjecture of Alon et al. that $d$ can
be at most logarithmic in $n$. We also show that our construction is best
possible, in the sense that an upper bound on $d$ of the form $2^{O(\frac{\log
n}{\log \epsilon^{-1}})}$ holds for all $\epsilon$ and $n$.
