In a game that's so frequently about combat, I'd say that increasing combat options and the benefits of tactical play, while reducing the importance of a strong character build by trying to eliminate the potential for overly sub-par character builds, would be a major step towards challenging the player rather than the player's stats.
I'm going to forego discussing how the basics of gaming haven't really changed, and coming up with a plan to save the city from the orc army is basically the same in 4e as it was in 1e since its all freeform player/DM roleplaying. I'm just going to talk about combat itself.
I can't really find a nice way to say it, so I'll just say it- I think that early edition D&D combat, viewed in a vaccuum, is terrible. Its all the fun of scratching off a lottery ticket, or repeatedly pulling a slot machine lever. I had some good times with earlier editions of D&D, but those good times almost exclusively occurred when we found ways to get around or ignore the combat system.
So many roleplaying games seem to be lacking the "game" part to me. Or rather, they make the classic Ameritrash error (MerricB knows what I mean by this, the rest of you can go to BBG and look it up) of assuming that, if you're simulating something cool, you must be having fun, without stopping to pay attention to whether the simulation itself is a fun game. Having a fun game is a key aspect of challenging the player rather than the character's stats.
You can denigrate it all you like- but rather than say that 4e is like a boardgame now, I'd say that 4e combat is like a good boardgame now, and earlier editions were often like poor ones.
I'm probably kicking off an edition war here even though I don't mean to. Read above again, I really enjoyed my Rules Cyclopedia D&D, I just thought the combat was poorly written once I had the chance to see a broader spectrum of gaming.