Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other doesn't. Can you tell in polynomial time which situation you are in? Obviously you can if graph isomorphism is easy or if finding Hamilton cycles is easy, so let's assume that they are both hard.

There may be a trivial answer, but it seems to me that the question is not obviously as hard as graph isomorphism, since if you can always solve it, it isn't clear that you can modify the algorithm to tell whether an arbitrary pair of graphs is isomorphic. If there isn't a trivial answer, then my guess is that the question is more or less as hard as resolving the P versus NP problem or the graph isomorphism problem, but maybe it isn't, since you're allowed to assume answers to those problems. Anyhow, the question has just occurred to me and I haven't yet found a reason not to like it, so here it is.