This is one of those topics I have a lot to say about. To me, difficulty and challenge is very important.
Examples of doing difficulty right - Devil May Cry, God Hand.
DMC is a challenging game off the bat, but how it handles difficulty - much like Bayonetta - really shines after you beat the game and begin harder difficulties. It's basically a New Game+ allowing you to start again with every powerup you've ever gotten. Except now, the entire game's cast of enemies is restructured.
Cannon fodder enemies are replaced by higher ranking versions of themselves. What used to be showstopper mini-boss enemies seldom encountered through the game now become common enemies. And those "Arena" moments now spawn far more dangerous enemies. It takes everything you've done through the normal game and forces you to master it all over again, with a challenge that actually feels fresh.
God Hand's adaptive difficulty is not only dynamic, but the way it affects enemies through the game is brilliant. Instead of remixing the game's enemies, replacing them with tougher versions of themselves, it takes the very same cast of enemies and makes each one of them far more dangerous. As difficulty rises, enemies gain more moves, attack faster and harder, dodge and counter your attacks, and attack far more aggressively. This turns basic low-ranking enemies into punishing obstacles, and high-ranking heavy hitters into nightmares.
Examples of doing difficulty wrong - Resident Evil 5, Gears of War.
Almost nothing changes in these games as you bump the difficulty up. No remixed enemies, almost no noticable change in enemy behavior. All that changes, is you take more damage, and deal less damage. Bam, the game is now 'Hard'. Aren't you feeling challenged????
To me, this is one of the most disappointing things a game can do. That is, cop-out on it's advanced difficulties. I like to find replayability in games that might not be inherently replayable, and I find a lot of replay value in harder difficulties. If the harder difficulty is the exact same thing as the normal difficulty... then that sucks.
In Gears of War, harder difficulties aren't about how GOOD you got at the game and how GOOD you handle weapons. It's about not getting shot. Which means spending even MORE time in cover, and spending even LESS time shooting enemies. Man, I sure feel like my skills are being both tested and proven.
RE5 probably has the worst case of artificial Hard-ness. As there seems to be literally no differences between Veteran and Pro at all. My friend and I actually had to handicap ourselves during our Pro playthrough just to actually feel a difference in challenge.
If we went through the game with our upgraded weapons from the get-go as the game implied it wanted us to do, then it actually would've been EASIER than it was in Veteran. Which is the exact opposite of what's SUPPOSED to happen.
I want my hard difficulties to feel like the game recognizes my experience with it, and actually mixes things up. That's why I loved how DMC and Bayonetta handle their difficulty. Even after you beat the game, you never knew just what the game was going to throw at you next, and just how much it was going to throw at you. Or God Hand where the same enemies behave differently, and the flow of every fight changes dramatically.
^If a game fails to match this sort of change in challenge one way or another, it tends to be one of those games I file under "Never replay again."