Task: Given $n$, find a generator of $GF(n)^*$.
Is there any evidence this is hard? Maybe a reduction from another problem presumed hard?
Finding the orders of elements should be hard because I think it can be used to find factors. The order of an element divides the order of the group, so if you pick random elements and find their orders then you can find random factors.
I'm not sure if deciding whether an element is a generator is hard, or if finding a generator (a weaker problem) is hard.
I will give a bounty to an especially good answer.
Yes, and no. There's no known algorithm for finding a generator, but your chances of picking one at random ($\frac{\phi(p^n - 1)}{p^n - 1}$) are "pretty good" (I can't recall the exact limit for this expression, but I believe it's somewhere around 46%).
It is not hard to see that this question is intimately related to knowing the exact distribution of primes amongst the integers, an unanswered question that remains of great interest to many (the asymptotic distribution is the best we have, I think).