Thomason's algorithm surely is superpolynomial, and shows that the problem is in PPA. In [3] I described another algorithm, also exponential and shows PPA, which is just as simple and has the added feature that it is easier to show that it is superpolynomial. Towards you question, given the way in which each of those algorithms behaves, I would very much suspect that finding a third Hamilton cycle given the first one is no easier than to find the second one. But I am not sure whether that helps to solve the related question: if you are given two distinct Hamilton cycles already, can you find a third one? Which I suppose is what you had in mind here.
[3] T.R. Jensen, Simple algorithm for finding a second Hamilton cycle, Siberian Electronic Math. Reports 9 (2012) 151–155.