Have you been upgrading weapons ASAP when you access them? There aren't many tiers, but each time you unlock more upgrade slots things go up pretty exponentially in power because a +10% damage boost makes quite a difference.
I think I used Override once through the whole game, to the point where I didn't even think about it while writing this whole thing.
Difficulty definitely adjusts damage (I started easy and switched to story because I was tired of whittling away at snapjaws in the open world). I know Story nerfs incoming damage (which I don't like), but I think the main adjustment above that is to outgoing damage. The fancy armor you get for collecting all the power cells also reduces how much of a shield it gives you before running out at higher difficulty.
Honestly I think they made stuff more expensive and give less shards when killing. I haven't been able to afford anything besides what's been gifted to me. Even with all the grinding I'm doing, I'm pretty broke.