Hmm ok, it seems your players want their cake and to eat it as well. :laugh:When I said "give them an arbitrary penalty" I meant that I would resolve the combat in a single attack roll for all players, and they receive a penalty to their attack bonus until they can rest, making multiple combat encounter over the course of an adventure very risky.
I do add flavor to my combats. The problem ain't the flavor, it's the lenght. My players don't want to fight. They feel it takes away time that could be used to advance the plot. They don't find it a source of suspense.
It's probably because I have difficulty to adjust the difficulty of the fight. When it's too easy, it's a pointless waste of time. When it's too hard, we might as well not play if we are going to fail anyway, and when it's in-between, well the time it takes to recover is debilitating to the story. ( I usually play in worlds where magic does not exist, so there is no healing spells or potion, only good old fashionned rest. I could play in a world that include supernatural, but it's not the same feel, and my players love the historical medieval theme there is in my games.)
So I usually don't do any random encounters. The only fight I do are when it's important to the plot, or when NPCs are actively wanting them dead. However, it's hard to have the NPC appear as a threat, it's difficult to make it appear competent if he send incompetent lackeys.
If you're playing in a historical type setting, meaning no magic and such, then I would play most combat like it was a social encounter.
If your guys are sneaking into a castle simply work it off of skill rolls rather then combat rolls.
The party attempts to enter Castle Ravenloft (god I miss Ravenloft). They find several guards at the gate.
DM: Rouge make a skill check to see if you climb the wall then I need a sneak check to ensure you're undetected.
Rouge: I pass and move to the first guard, I slash him across the throat with my dagger.
DM: Roll grapple check and then an attack check at a negative penality.
Rouge: I got (randon roll) and (random roll). Whats the deal.
DM: You take him down and kill him but you caused enough noise for another guard to over hear you on the battlements, he's heading over to check things out.
Ranger: I fire my bow hoping to take him in the neck and kill him.
DM: Roll at a negative multiplyer...
You get my idea.
Start dealing wth combat like you would with bluff, and other similar skills. Only use the normal D&D type encounter for the large scale plot combats, rather then every combat.
I would also recommend letting the first round of combat going normally then adjusting the numbers as you need it to the encounter. If you make an encounter where you're PC's are shruging off damge from the bad guys turn it up on the next turn. If they're getting spanked turn the damage down.
Personally I don't think D&D is the best ruleset for that type of game, especially in 4th edition. 2nd or 3rd edtition sure but 4th really focuses on combat. If your guys prefer the Social/Story heavy games you may have more fun with games done by Whitewolf or Fantasy Flight.