Instead of adding a death penalty which, BTW is also a good alternative, how about adding a good play reward system? You get bonuses for not dying, finish the mission in a certain amount of time, etc, etc. You could add a sliding bar for difficulty and as its increased the reward for "good" play would increase. Just an alternative idea for all those people out there hat don't want any type of death penalty. BTW this system would work great with a DEATH penalty!! :p
This is a pretty good idea. I also don't think a death penalty is a good idea, but dying just kind of needs to work differently. In PvP, you should spawn in waves like every other PvP game. There's a reason it does that: it gives some rudimentary organization to pugs. The waves should also be spaced a few minutes apart so that dying is actually a bad thing.
In PvE it should reset you to your last checkpoint, meaning the enemies past that checkpoint respawn.