The best answer will eventually be what you and the rest of the players find the most _fun_, so this is my take on how I deal with characters that die.

## There has to be a penalty, for fairness sake

First off, I always let them roll a character that's below the least experienced PC in play, rounded down. If the rest of the party was level 5 but halfway to 6th level, I let them be at the beginning of the 5th level.

If they were all brand-new 5th level; I'd go for 4th level, or maybe halfway from 4th to 5th.

Why should there be a penalty? First, I agree with you in the sense that death should be a serious aspect; having a penalty is a serious consequence.
> Plus it could perhaps make death seem rather trivial, if the player can simply return to the scene with a different character of more-or-less equal power.

And another possible issue here is that other players may feel like it's _not fair_. And if it happens often, it starts to get boring. And in my experience you tend to feel like your partner is just not taking it seriously.

## Players get attached to their PCs

In reality... I've rarely had a player roll a new character because of death. They usually become attached to their PCs, so they'd rather have their friends raise them. It might be a little boring for such player in the meantime, but in my groups they usually just go with it and cross their fingers with nervousness and anticipation.

BTW, this gives me a good opportunity to strip them of some extra gold they might have gathered (I'm usually too easy going and give them too much gold).

### There's also a penalty here...

In ADND, the _Raise Dead_ spell indicates that the character will lose 1 point of their Constitution score (if they make it at all). So there's the fairness/balance bit in the rules, IMO.

## Remember Rule 0

[Rule 0](http://rpg.stackexchange.com/questions/22715/) is that you, the GM, should have the final authority on what goes and what doesn't. But don't forget the _reason_ for that rule: It's all about having fun.