Right up front I'll acknowledge that this perspective is not universally held. There are numerous reasonable alternatives to this, including enjoyment of the voyage of discovery, a primarily social focus, or just a desire to blow of steam. With that in mind I want to be clear that I'm not presenting this as how things should be done, only as something I (and, I think, a non-trivial number of others) want in games and how i think it can be accomplished. If you reject the premise, no harm, no foul.
Now, classically RPGs have introduced challenge by making the game more difficult. This has clear roots in the wargaming table, and it makes things challenging for the character (through bigger monsters, more damage and such) as well as for the player (with puzzles and traps that depend on player cleverness or knowledge to resolve). This is a tricky balancing act; if the ratio of player vs. character challenge skews too far one way or another then it can turn into a mess.
For a lot of players, this is their sweet spot, and there's a lot of literature and lore dedicated to hitting it just right. From my perspective, a great deal of the old school Renaissance is targeted at hitting this window, and much of the reason they reject subsequent visions of D&D is because they go too far off the point of balance (usually towards more character challenge).
For some players, however, this all gets a little too meta. To properly pull off this kind of balance often requires keeping the "game" part of play very close to the surface, whether it's in the form of common resurrection or riddles based on 1970's tv shows. Perhaps even more, this is a player-centric model, and it works less well when you want to put the character in a more pre-eminent position.
That thinking presented difficulties as new structures of games started showing up, most notably Vampire. The problem was that the dungeon was a finely tuned machine of challenge, and stepping away from it left GMs at a loss. Some games addressed this by simply re-skinning the dungeon into spaceships, haunted houses, corporate offices or what have you. Some added on a layer of abstraction to try to structure non-dungeon events like a dungeon (usually by imposing unreasonable restrictions, and creating the basic model for "railroaded" adventures).
But all those tricks could only go so far, so a new method of introducing challenge came along: Obscurity.
It turns out that if you give players free reign but keep them on a very restricted diet of useful information, they tend to freeze up, or at least limit their action to the known range of options. By turning the valve on secrets, you could keep things hard, dole out rewards, and generally make your players dance like rats in a cage.
Obviously, I'm not terribly fond of this model, but I concede it had some strengths. The one thing that was required for this approach to have any teeth was, paradoxically, a very richly defined world that the players could invest in. The element of mystery left hazy spots to be filled in by the imagination in ways that were far more compelling than the reality of the game could ever be. By giving a high level vision for players to sink their teeth into, the GM could engage in the worst kind of sleight of hand at the table without raising too many hackles because, hey, awesome background and total freedom, right?
Another interesting choice for challenge has been to challenge the creativity of players by granting them a great deal more authorial control and by offloading traditional GM responsibilities. This is an interesting solution because the bad outcome is rarely something that happens in game so much as the game (or story, depending on perspective) falling flat. This is an interesting idea, and it's easy to take in directions far afield from normal gaming, but it's definitely a specialty track.
My favorite method for making a game hard is to make it compelling. That is, create a game with strong enough player investment that in-game consequences matter to the player enough that when the player makes empowered choices in play, they have meaning. This is an interesting thing to contras to traditional difficulty because this model works even if players NEVER FAIL. Success and failure have their place in the picture, but the game is made hard by making the choices hard.
Now, for all that I distinguish between these approaches, and as much as they can seem like armed camps, the important thing to remember is that none of these are mutually exclusive. A good game may lean towards one pole or another, or even stick primarily with one, but it is a rare game that could not benefit from occasionally dipping into the other sources of challenge to mix things up.
1 - Perhaps more accurately, 'challenging.'
2 - The point, after all, is to engage the player. The character is merely an agent to that end.
3 - The ill-informed tend to categorize this as "Roleplay vs. Roll-Play" (usually followed by a passable yokel laugh) but it's much more nuanced than that. Both camps savor roleplay, but it's position of preeminence (compared to other elements of play and fun) is subject to re-arrangement within the hierarchy.
4 - The real irony, to my mind, is that the emphasis on player challenge puts this approach very much in tune with the OSR's goals, while the methods are so much at odds I constantly expect dance-fights to erupt between the groups.
5 - That is, choices that matter to the game, as opposed to choices that only seem to matter to the game.