I stealthed in all my encounters at first. I had the markings and all that still on and marking is lenient as hell. You can just point in a general direction and spam L3 and they'll all be marked. It was fun to stealth the first couple of dudes and then start blasting them since the gunplay is so good.
Yeah, I did have issues with the pacing and story. The gameplay is the best the series has ever seen hands down. Playing through the story and watching the cutscenes, I was just thinking how much Druckmann had drunk the TLoU kool aid. I don't want to give too much of a spoiler, but when they said the story was more grounded, they fucking meant it, which could be good or bad according to who you talk to. (I didn't like it.)
The wide linear approach to combat is great. It kinda doesn't have to do with the story and I don't feel like it had a negative effect to the story or pacing.
Some parts, especially towards the end (UC2 syndrome) drag on way too much, but I don't think that has anything to do with the wide linear approach.