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).
- 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 - P iff NEXP is not equal to EXP. So assuming NEXP is not equal to EXP, the padded version of any NEXP-complete problem is of intermediate complexity. (Such a set cannot be in P unless NEXP = EXP, contradicting our assumption.) There are plenty of natural NEXP-complete problems.