Here is a list of problems that may or may not qualify as "sufficiently" different. By the same proof as for Graph Isomorphism, if any of them is NP-complete, then the Polynomial Hierarchy collapses to the second level. I do not think there is any broad consensus as to which of these "ought" to be in P.
- Graph Automorphism (determine if a graph has a nontrivial automorphism). Reduces to Graph Isomorphism, but not known (not thought?) to be GI-hard.
- Group Isomorphism and Automorphism (where the groups are given by their multiplication tables). Again, reduces to Graph Isomorphism, but not thought to be GI-hard.
- Ring Isomorphism and Automorphism. In a sense, this is the grand-daddy of all the above problems, since integer factoring is equivalent to finding a nontrivial automorphism of a ring, and Graph Isomorphism reduces to Ring Isomorphism. See Neeraj Kayal, Nitin Saxena. Complexity of Ring Morphism Problems. Computational Complexity 15(4): 342-390 (2006). (Interestingly, determining if a ring has a nontrivial automorphism is in $P$.)
- This post by Bill Gasarch contains some other problems with the taste of Ramsey theory that look like they might be intermediate.
- By Mahaney's Theorem, no sparse set can be NP-complete. But we also know that there are sparse sets in NP$NP$ - P$P$ iff NEXP$NEXP$ is not equal to EXP$EXP$. So assuming NEXP is not equal to EXP$NEXP \neq EXP$, the padded version of any NEXP$NEXP$-complete problem is of intermediate complexity. (Such a set cannot be in P$P$ unless NEXP = EXP$NEXP = EXP$, contradicting our assumption.) There are plenty of natural NEXP$NEXP$-complete problems.