What is the most efficient algorithm for deciding if an element is the least in its orbit?
For general equivalence relations, not those arising from permutation group actions, even finding lexicographically least is still "too" general. Finding the lexicographically smallest element in an equivalence class can be $NP$-hard (in fact, $P^{NP}$-hard) - even if the relationship has a polynomial-time canonical form [1].

However, for permutation group orbit problems as you describe, deciding whether two points lie in the same orbit is not likely to be $NP$-hard: it is in $NP \cap coAM$, and hence not $NP$-hard unless the polynomial hierarchy collapses to the second level.

A canonical form for graph isomorphism is also a special case of the second problem you state. The best known canonical form for graph isomorphism runs in time $2^{\tilde{O}(\sqrt{n})}$ [2].

Since you said in the comments that any canonical form will do, you might also be interested in my paper with Lance Fortnow [3]: in its currently generality, I think your question is related to our results. We show that if every equivalence relation decidable in $P$ has a canonical form in $P$, then "bad" consequences result, such as $NP = UP = RP$, which in particular implies that the polynomial hierarchy collapses down to $BPP$. On the other hand, the equivalence relations you're interested in may not be in $P$, but this result suggests that even if it lies in a higher complexity class other hard problems may still stand in your way. 

So I think if you want some better upper bounds you really need the problem to be more specific.

[1] Andreas Blass and Yuri Gurevich. Equivalence relations, invariants, and normal forms. SIAM J. Comput. 13:4 (1984), 24-42.

[2] László Babai and Eugene M. Luks. Canonical labelings of graphs. STOC 1983, 171-183.

[3] Lance Fortnow and Joshua A. Grochow. Complexity classes of equivalence problems revisited. Inform. and Comput. 209:4 (2011), 748-763. Also available as arXiv:0907.4775v2.