How about the most basic challenge of all: making a competent character? (Seriously, sometimes I think the only difference between challenging the player and challenging the character is whether the challenge is direct or indirect, through the character creation mini-game.)Humour aside, there are quite legitimate ways of having the game challenge a player; none of them physical. Puzzles, riddles, etc. all challenge the player to a) think like the character and b) solve them. Social situations can similarly challenge players quite well.
Taken to extremes, the philosophy of "challenge the player, not the character" raises the question of why you need a character to play in the first place. If the player is the one solving the puzzles and riddles and interacting with the NPCs, then the character really is nothing more than just a collection of combat statistics and magical "I win" buttons.