Yeah, you definitely want a balance. You want obstacles that make sense. The worst is games that are arbitrarily hard. Like just ramping up the hit damage of an enemy so that you die instantly, or having impossible controls. (although, some b-games that do that are awesome, because they're so insanely challenging and weird) You also want to ramp it up in a fairly smooth way so that the player can grow with the game / characters.
Its hard stuff to get right, especially because everyone is at different levels of play ability. One way is to offer people alternate paths and/or solutions, so that players that may be more interested in exploration don't have to be doing combat all the time, etc.
Its a tough balance, that's for sure!