I don't care much for penalty, take a look at Abe Oddworld games, which the only penalty for dying was restarting from a checkpoint.

In my opinion, difficulty should be skill, and skill alone. What do I mean by skill? It is the ability to analyze your current situation, and apply the correct techniques to increase your chance of success.

I'm going to use a battle situation, since most players can relate to it.

Ever heard of the phrase 'knowing is half the battle'? Obviously, we can't always know what is going to happen when we encounter a "new" monster. However, overtime by battling the same monster you will gain knowledge about it, which would better help you analyze a live battle situation.
E.G. Peiste has a cone aoe attack, you would keep an eye out for it when it is charging up an attack. When you see it's eyes glowing, it is executing a paralyze attack, you should keep your paralyna ready for a quick response.

When everyone actually plays their best move in a battle situation, everyone can feel good about defeating a DIFFICULT monster.