  Let $\chi$ be a primitive character modulo a prime $q$, and let $\delta > 0$.
It has previously been observed that if $\chi$ has large order $d \geq
d_0(\delta)$ then $\chi(n) \neq 1$ for some $n \leq q^{\delta}$, in analogy
with Vinogradov's conjecture on quadratic non-residues. We give a new and
simple proof of this fact. We show, furthermore, that if $d$ is squarefree then
for any $d$th root of unity $\alpha$ the number of $n \leq x$ such that
$\chi(n) = \alpha$ is $o_{d \to \infty}(x)$ whenever $x > q^\delta$.
Consequently, when $\chi$ has sufficiently large order the sequence
$(\chi(n))_{n \leq q^\delta}$ cannot cluster near $1$ for any $\delta > 0$.
  Our proof relies on a second moment estimate for short sums of the characters
$\chi^\ell$, averaged over $1 \leq \ell \leq d-1$, that is non-trivial whenever
$d$ has no small prime factors. In particular, given any $\delta > 0$ we show
that for all but $o(d)$ powers $1 \leq \ell \leq d-1$, the partial sums of
$\chi^\ell$ exhibit cancellation in intervals $n \leq q^\delta$ as long as $d
\geq d_0(\delta)$ is prime, going beyond Burgess' theorem. Our argument blends
together results from pretentious number theory and additive combinatorics.
  Finally, we show that, uniformly over prime $3 \leq d \leq q-1$, the
P\'{o}lya-Vinogradov inequality may be improved for $\chi^\ell$ on average over
$1 \leq \ell \leq d-1$, extending work of Granville and Soundararajan.
