At that level the paladin has 6 spells; he needs to blow at least two of them to compete with that damage. Then he can do it two more times, in the same combat even, or use those spells for something else. If he chooses to space them out, he can smite twice probably every time the fighter action surges in a typical adventuring day (six encounters, two short rests). In a couple levels, the paladin is doing the smite nova rounds even more often than the fighter can action surge. And if he doesn't use them as smites...look at all the other cool stuff you can do with spells. Yes they're dailies, but the paladin gets a lot of them; in practice action surge is much more use limited than a Paladin's smites. The barbarian likewise doesn't need to match the nova of action surge because he can do it again and again and again, from round to round, even without frenzy.
At that level, Paladin might get more with those two spell slots without advantage, but they're going to have to spend a at least one more to catch up on one turn with advantage. And keep in mind, that's still all of your 2nd level spell slots, and perhaps one of your level 1 ones, in addition to not factoring in comparison to potential resources like superiority die which themselves are essentially an additional 18 damage per short rest until level 7, at which point it becomes an additional 22.5, all with packed in combat utility to boot. If a Fighter is actually using all of their resources intelligently, there's no way that a Paladin would keep up over the course of a day, and they'd have to put in a very serious effort just to keep up for one fight.
By level 6, Fighter gets another ASI. In terms of the value of that, increasing your primary offensive stat from +4 to +5 at that point adds about 3.2/4.1 damage per round (assuming GWF/GWM, in this case) to your attacks (in addition to improving saves, specialized combat actions, and non-combat abilities). This does more than the duty of allowing Fighter to keep up with a Paladin's output over the course of a day. Paladin gets a bit of a bump at level 9 that makes it more competitive with Fighter's ability to action surge, thanks to its level 3 spell slots. However, any competition there gets cut back down at level 11 and on.
Compared to a Barbarian, the results are even more in the Fighter's favour. If we're not going to be factoring Frenzy (and we shouldn't, because it sucks), then past level 6, the Fighter starts to outdo a raging (daily resource) Barbarian with just normal attacks (assuming advantage; without advantage, just spend the dice and trip the guy...or just flank him, make it your own), no resources spent. And it will continue this way for the rest of the game, with the gap only getting considerably larger with each tier of play.
No matter how you cut it, Fighter's damage output just isn't an issue. It will consistently come out as the overall highest damaging class in the game with little effort. While I'd argue that Paladin is still the best martial class in the game, and perhaps one of the best classes in the game, period, with considerable room open for multi-class abuse; its damage output in comparison to Fighter isn't really the core of the issue, and definitely not Action Surge (and for its worth, we really shouldn't try to put every class on the same level as what Paladin or, more specifically, what a fully developed multiclassing Paladin is capable of, because the results would be ridiculous).
Action surge is great...it's often a great dip because it's better for other classes (particularly spellcasters) than it is for the fighter. But it's not the round action surge is up that's the problem. It's all the other rounds, where the fighter, whose thing is supposed to be superiority at combat really doesn't feel all that superior.
The Fighter effortlessly does damage that allows it to keep up with every martial class in the game, and once it applies its abilities, should have no trouble surpassing its competition. A Paladin blowing its load all at once might be able to take down the BBEG faster, and this can definitely be an issue (especially if he manages to kill the guy before the rest of the party gets to act), but overall, the Fighter is always a top level contender, with a fantastic mix of consistent damage output and nova potential.
It is disappointing that Eldritch Knight archetype only gets the two schools to draw from, leaving it with no true offensive tool until Haste at level 14 (but what a tool!). And it definitely should get access to a wider spell list (honestly, evocation makes absolutely no sense to what I imagine from an Eldritch Knight), but the core of the class itself is solid, and functions perfectly fine.
