As one of the 13th Age Paladin's most vocal critics in those arguments, I'd say that the problem is more that the class is boring as opposed to underpowered. Even with Smite Evil, our group's Paladin is easily the least offense-oriented in the party (which includes a healing-specced Cleric that is by no means a heavy-hitter, but deals more consistent damage). A lot of my monsters can only hit him on a 16 or 17 though, especially if he's got an AC buff from the Cleric or if he slaps a Rune on his armor. And even once they hit him, the damage dealt is often just a drop in the bucket compared with his total HP. When I throw the really nasty monsters at the party, the Monk and Cleric might go down in one hit unless they're already at full, the Fighter can take a little bit more, but the Paladin just WILL. NOT. DIE. Even when he's funneling extra damage toward him with Bastion.
Between the aforementioned Bastion and Paladin's Challenge he's also a pretty incredible "defender," but the design is still too simplistic. A defender-specced Fighter tends to be more "active," particularly with Skilled Intercept and maneuvers like Shield Bash. Heck, even Tough as Iron which is a pretty simple concept (Rally as a quick action) comes across as "active" because you still get to DO something on the round when you Rally.
Not that I think there's anything inherently wrong with simple classes...if you like to play simple classes. I just think that there needs to be options for tweaking up the complexity dial. The Cleric spell/domains are one way, but the Cleric class is VERY daily-heavy, so you're trading a talent or two to get a daily ability or two. Which doesn't help that much during the majority of rounds (where you don't drop a daily), and given that Talents are the Paladin's only resource besides feats (which usually modify talents) and "bigger numbers," well as you can imagine it only helps so much.
Compared with the other simple classes, the Ranger can pick up an animal companion, and has talents to grab spellcasting from TWO different classes. The Sorcerer has a better range of spells that can be picked up (especially if you want something other than a daily), and the feat that modifies the steal-a-Cleric-spell is MUCH better for the Ranger than it is for the Paladin. The Ranger gets ANOTHER spell in the form of Heal once per battle as an Adventurer feat, whereas the Paladin just gets to use Cha in place of Wis as an Adventurer feat (which won't even DO anything for some Cleric spells), and it's not until Champion tier that he can pick up a feat to get Heal. Except that it's twice per day, instead of once per battle.
Even the Barbarian, the professed "simplest of the simple," has some interesting toys to play with. Whirlwind offers a significant enough trade-off that there will be some meaningful decision-making to be had, Slayer offers the opportunity for a really dynamic fighting style with several decisions that need to be made each round (do I roll the dice with a disengage, or just suck up the opportunity attack? Is the bonus damage worth NOT focus-firing? Who should I target in the first place (ranged enemies with a bow or crossbow won't have a hand free to make an opportunity attack)?). Unstoppable has that balancing act of using it when needed vs when you're most likely to actually hit with it. And Rage, while a decision of similar complexity to Smite Evil, has a bigger, longer-lasting impact and by nature of its more limited use has bigger resource-management implications.
Though while we're on the topic of Barbarians (as if this post weren't long enough), if anything they're the most underpowered class in the game. They hit like a truck, sure (when they're Raging), but they're intolerably squishy by RAW (at least IME). The simple house rule I've used is to boost their base HP up to 9 to make up for their extremely low AC.