For me, a game needs a difficulty curve to be enjoyable. If it's all a breeze, then I finish it and move on without another thought (or even become bored with it before finishing it).
It doesn't need to be crazy hard 100% of the time, but it's those moments where I run into a roadblock, and have to re-evaluate the situation and develop new strategies. It's exciting when I get positive results, and very satisfying when I overcome the challenge, creating lasting memories.
The first time I encountered the yellow devil in Mega Man, he rocked my socks. After enough attempts I realized there was a repeating pattern, and then it was just a matter of nailing the execution. After beating him, subsequent play-throughs were rather easy with the knowledge I gained, but still engaging knowing that if I got sloppy he'd get the win.
That said, it has to be a fair challenge - if the game is just broken, or skewed in a fashion to incentivize the use of microtransactions, then I'm out after realizing it.
If the challenge is indeed fair and just requires better strategies or expert execution, then I can keep at it for hours/ days/ weeks. I spent countless nights on Champion's Road in Super Mario 3D World when it first came out on the Wii U. It was so difficult, but I knew that I could do it. The pay off when I did made completing the game all the more fulfilling.