Waiting for health regeneration is boring, yes. However, if I spend 80% of my play time waiting for the right moment to make a move, earning the occasional perfect victory... It might be a very intense, exciting and satisfying 80% + 20% (complete game experience) we're talking about. Hideous Destructor goes a little ways in that direction. To get any further in that direction you'd probably need more ability to predict or observe activities in unexplored areas. (And hey presto, we're playing Commandos: Behind enemy lines.)
You could also have a regeneration system where your automatic regeneration caps based on how low your health has been, with healing items restoring health and/or max autorecovery. Fast recovery during fight is not smart, but fast recovery to a cap between fights gives you some extra durability without making the individual fights too easy, and without making you wait much at all.
I don't know... Maybe. An idea anyway.

