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 balance's 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 they're also having to put up with the consecuences. 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.
Or like SevenSidedDieSevenSidedDie put it:
The balance of power for characters is generally against the world, not each other, and cooperation is the default. Without a penalty for death, however, the world becomes meaningless, toothless, and the game is robbed of its essential point.
It's also worth noting the point made by Hey I Can ChanHey I Can Chan: Without penalties the system could be abused in the same way video games define start scumming.
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 balance bit in the rules, IMO.
Remember Rule 0
Rule 0Rule 0 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.