Complexity of Computing Lexicographically Minimal Element of Orbit
This problem is NP-hard.

Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world looks, finding the lexicographically least isomorphic string is NP-hard. This is precisely the content of Proposition 3.1 here. In fact, they show it remains NP-hard even when $G$ is an elementary abelian 2-group (=every nontrivial element of $G$ has order 2).