Nit: It's only hard to find _hamiltonian_ cycles, finding general cycles is trivial. More generally, it's hard to find long simple cycles (a simple cycle is one with no overlapping vertices visited twice).

I don't know how hard it is to generate graphs that are hard to find simple cycles in though. For example, previous work showed that random graphs are likely to contain hamiltonian cycles (and with this algorithm they can now be found).