A seriously under-rated hero, especially back at the time of his original release. To be honest I think the biggest reasons people underestimate Boromir are firstly that some people love Boromir a bit too much, and secondly that a lot of people wanted him to just be the Gondorian equivalent of Dain Ironfoot. Given that I just named possibly the two most powerful heroes in the game, it's small wonder he didn't quite measure up.
But let's leave aside what he isn't and talk about what he is. Now he certainly isn't the only way to build a Gondor deck. He synergises with Visionary Leadership, but you can equally put it on a different hero. So consider him on his own ability. Well, for one thing, unlike Dain, he can actually take actions while keeping up the boost. Holding onto a spare resource in the sphere with Steward of Gondor is not that big a hardship compared to keeping one of your three heroes ready all the time. And a constant, global boost? Obviously outside of Battle questing it's only good for combat, but oh boy is it really good for combat. You can look at the allies who are powerful already, like the now 4 Knight of Minas Tirith, the 3 Veteran of Osgiliath (4 in Valour); or on the other end you can look at allies like the Squire of the Citadel or Errand-rider, who usually have no use beyond chump-blocking or in the latter case moving a resource, but now here they can do something else when you don't require those things. Boromir's boost allows you to have a relevant combat presence basically regardless of which allies you draw so long as you draw some, because an army of usually wimpy 0-1 allies who are now 1-2 will add up pretty quickly (and handily they're cheap).
In the end I think the biggest piece of advice I can give to people who're skeptical about Boromir is what I said at the start of that second paragraph - look at what he is, not what he isn't. He isn't Boromir and he isn't Dain, but most heroes aren't either of those two either, and that doesn't stop them being good. Nor does it stop Leadermir being good