Ha! I know exactly who you're quoting with those criticisms! That probably means I spend too much time here...
Anyways, the only beef I really have with Paladins is that the more situational/reactive utilities(the spells mostly) spend a lot of time unused when your party has a given fight well in hand. In progression, Paladin can certainly be the best thing ever (TM) , but it's just so odd to end up pressing fewer buttons once that progression ends.
Either way, I'm firmly of the opinion that the more boring someone believes Paladin to be the less they've ever considered trying the utility. There was a Vault run I did just after getting Clemency where I saved the party at every boss fight in ways only a Paladin can. I told the FC that this must be what it feels like to... Palawin :P
Hm? HG can totally stop magic! My group's Akh Morn strategy was light cooldowns for 1, heavy cooldowns for 2, Holmgang+Cover for 3, HG for 4, and every cooldown+praying for 5(but we didn't usually reach this one hence using HG on 4 instead of here).
There are just some specific mechanics that say FU to the "invincible buttons" but they eat through all of them. The Ramuh EX Tank Swap mechanic is a good example of this.