I'd like a lean system added on (my own idea for a vaguely related game concept includes the new Medal of Honor cover system and leaning outside of that), but the cover system tends to make things easier since you can see exactly what parts of your body are sticking out (an impossibility in first person orientation, as you don't have any sense of awareness of where any of your body parts are) and lets you blindfire. Human Revolution actually made the smart decision of having almost no accuracy during blindfiring (even in Gears of War is just serves as a "less accurate normal shooting"), but it does suit a more rapid combat style where you can respond to enemies in cover by running up, ducking behind the pile of boxes they're hiding behind, and blindly sticking a shotgun over and into their face when they pop up.
Isn't that more to do with 1st/3rd person perspective that a cover system? I imagine being able to switch to 3rd person would solve that problem, even with just the leaning and no real cover system. You wouldn't have blindfire, but ah well. I suppose it's a preference thing in the end.
On my second point, the training levels in the first game were downright ridiculous and completely destroyed suspension of disbelief: an augmented supersoldier and trained government agent can barely even hold a weapon steady enough to hit the target at 50 yards unless he decides to use those augments to increase his skills to the levels of an average USMC rifleman? Along with stretching believability even if you tried to justify it, it's immensely frustrating for players who have the skill to do the task (and could probably accomplish it themselves in real life) but are hamstrung by their character shooting like a drunk. Adam Jensen starts with the level of training and skill that someone in his position should rightfully have, and the augmentations do exactly that: augment his ability. He can use his Praxis points to steady his aim or reduce recoil, but he never needs to use them just to get himself past the competency level of your girlfriend trying out a shotgun for the first time out in the woods.
I wasn't trying to compare Human Revolution and the original (as I've never played Human Revolution), I just discussing the merits of the original's mechanics. I suppose I should've been clearer about that.
In any case, the incompetence at untrained levels aren't there for story purposes (because, as you said, it makes little sense), it's for gameplay reasons. You want to put all of your points into hacking and lock picking? Well then, you'd better be prepared to find the stealthy, break-and-enter-y solutions to things, because you're not going to last five seconds in a firefight. As I said, if you could overcome not levelling the relevant weapons skill with simple player competence, then there'd be little point in upgrading weapons in the first place, and every imaginable build would be a viable frontal attacker. Deus Ex is designed from the start to force you to specialise in a narrow set of skills and to have to use those skills to solve any given problem. It's so that you can't just say "fuck it, I'm just going to blast my way through the level".
Regenerating health became popular for good reason: limited supplies. Both games are infamously lethal (even on the easiest difficulty, HR will kill you quickly if you get caught in the open for mere seconds), but forcing the player to rely on limited medical supplies very often resulted in the player being caught with too little health to make it through the next section, but no supplies available to revitalize them. It's extremely annoying, especially since both games make such useful items in general relatively uncommon and have limited inventory space to try and fit everything in. Making it through Deus Ex gets frankly annoying sometimes, because you die quickly (especially early on) and you may have absolutely zero chance of recovering any health if you manage to hide. It's all in the name of giving the player a fighting chance, which is kind of a necessity if you want your game to have more than niche appeal these days. It's why my own game concept follows the Dwarf Fortress or Nethack manifesto of extreme unfairness and forcing creative thinking, but also understands the game's niche and how it's not meant to really be made for mass consumption.
Regerating health became popular because it works really well for linear shooters. There's little to no scope for searching for health pick ups, and it means the developer knows the player will always be on full health going into any given fight. Because those sort of shooters are all about creating a very controlled spectacle, it makes it much easier to design a level and place enemies in a way that's appropriately challenging without fucking up the difficultly curve. Since Deus Ex is not linear and is very open and player driven, the biggest merit of regenerating health no longer applies.
As for your experience, it sounds like you simply need to switch up your tactics. Medkits are fairly common if you properly explore the levels, they only take up one slot and stack up to fifteen at a time. The Medicine skill is relatively cheap and allows you to squeeze more health out of each medkit. Items like ballistic armour and thermoptic camo can be used to give you an edge in combat, augmentations like aggressive defence and ballistic resistance can turn you into a fucking amazing tank, especially if upgraded and of course the regenerating health augmentation can convert bioelectricity into health (and bioelectric cells are even more common than Medkits, and you can carry up to 30 of those at a time). Maybe it's just the build I went for, but by the time I reached Hell's Kitchen, I was finding more medkits than I could carry. The only thing that was in short supply was lock picks (for some odd reason, I was swimming in multitools). That's on the 2nd highest difficulty.