Find Hamiltonian cycle in polynomial time
Perhaps the most comprehensive list is available via ISGCI, along with references. Examples for which the problem is easy include bounded treewidth graphs and many subclasses of chordal graphs.

As to why exponential time seems unavoidable in general, we don't strictly know. As far as we know, P = NP is also possible.