I wonder if it's because it forces us to use a heuristic. By making the problem NP, our brains can't perfectly solve it. The more you play, the better heuristic your brain develops. But there's always room for improvement. You can always do a little bit better if you just keep practicing, keep your brain developing more neural pathways for a better heuristic.

Whereas if a game is in P, your brain can completely solve it, and then it's not fun anymore.

I wonder if this complexity–funness relationship extends to other complexities, like EXPSPACE.