While there are certainly plenty of parlor tricks and other illusions, I think in the best case, a game can contain a finely tuned learning experience, where by training you actually do get better at something. (Often something unimportant, but still fun.)

Throwing people into the deep end of the pool usually doesn't work so well. Scaling down the difficulty helps, but really what you want is challenges that teach you something. And you don't really need AI for that.

Last year I started learning to play accordion out of a method book. It has a bunch of songs ordered from easy to hard, and they're also chosen to teach certain skills. It reminded me quite a bit of good level design.