"This plan fell apart about three hours in when I met the first boss fight and realized the game expected me to fight a guy in the open, on a bridge, surrounded by henchmen, in broad daylight, with no possibility for a surprise attack."
This is wrong. You can defeat the first boss by sneaking up on him, there's even an extra 350 EXP for doing so.
As for Omen Deng, he barely takes any damage from bodyshots, but headshots take care of him quickly. Using the armor-piercing ammo type of your preferred weapon also helps (phosphor for shotgun, APD for assault rifle, steel core for pistol, high velocity for SMGs).
"This could have been the next Deus Ex, but it feels Serious Sam."
Shamus, I have a lot of respect for you. But you either wear oversized nostalgia goggles right now or you're making a misleading statement deliberately to get more attention. I'll give you the benefit of doubt and guess it's the former.
The bosses in Deus Ex had a load of health as well and you couldn't sneak past any of them. You could run away from one of them and defeat another one before combat started by an alternate method (which required you to take the right choice in a sequence that happened much earlier, though). So your point that AP isn't a worthy spiritual Deus Ex successor because of forced bosses that can take a large amount of punishment simply doesn't hold up. Because Deus Ex did exactly the same thing.
On a more general note, I don't see why people rip on the imbalanced skills in AP so much. Sure, it would have been better if shotgun was actually a viable weapon on hard difficulty, but I can't think of any other game with RPG-elements where you can't screw yourself over (or at least make the game considerably harder) by picking the wrong skills.