They're just penalties for the player and bonuses to the monsters.
You'll face the same monsters, traps...only you'll be weaker and they be stronger.
I think that is a bit 'meh'.
So here's my main idea:
Nightmare and insane would not affect healing or damage suffered/dealt directly. Instead....they would would significantly increase the level of all dungeons but not the exp received(and perhaps make the loot dropped by foes inferior, too? Actually might not be needed, as good loot needs proper stats to equip anyway).
This means FAR more than numerical penalties to the player and bonuses to the enemies.
It means you'd face DIFFERENT creatures/traps and challenges.
For example, on Insane you could regularly fight Elite Skeletons in Amon Sul instead of normal ones, perhaps even Huorns in the Trollshaws.
You could fight drakes where at 'normal'difficulty you'd get hatchlings and so on.
Your enemies would be more challenging - not because they get a +damage% bonus or because you have a penalty, but because they're DIFFERENT and with better talents/special powers.
I also had two other ideas:
1)Higher difficulties could disable/nerf stuff like healing potions, escort quests, shop use...
That would make the player who want a real challenge happy without making the game harder for everyone

2)Some sort of 'hardcore'/'speed'/'heroic' mode that works similarly to the main idea(higher dungeon level), with a very important difference - you DO get the better rewards from facing more powerful opponents, mainly exp.
That would let you level up faster if you can survive(and thus gain more flexibility/cool talents), but you'd still have to face more more dangerous challenges.
Not a real difficulty but an alternate way to play the game - which I do realize could slightly overlap with the 'Infinite Dungeons'campaign.