First, because some fighters might choose to focus differently. They might think that Great Cleave (like Cleave, but without the 1/round restriction) is better than Weapon Specialization. There is something to be said for not putting all your eggs in one basket hilt, particularly in 3.5e where it was pretty common for monsters to have damage resistance you needed a particular material or damage type to overcome. So it might be a good idea to have both a cold iron battleaxe and an alchemical silver warhammer, but you might not want to spend the feats to specialize in both. Being the Swiss Army Fighter who always has the right tool for the job can be fun.
Second, because the Greater versions were a patch. The 3.0 PHB did not have Greater Weapon Focus and Greater Weapon Specialization, just Weapon Focus (which wasn't fighter-exclusive) and Weapon Specialization. I don't remember if they were added in a 3.0 splatbook or if they were new in the 3.5e PHB.
The fighter has a number of open feat options (the ones everyone get, at level 1 and every level divisible by 3) plus a slightly larger number of feats (level 1 plus every even level) that have to be combat-relevant. The paladin has the same number of general feats plus a bunch of class features that generally don't make them better at fighting, and is additionally hampered by needing to put resources into increasing two stats that don't do anything particular for fighters.
Now, can you make a fighter who chooses to spend their options on not fighting? Yes. Is that likely? No. Is someone who does that likely to be overly concerned with the balance between a fighter and a paladin? No, and if they are they only have themselves to blame.
I don't care about blaming people, I care about the claim. The statement was "Fighters are always better at combat than Paladins, who rely on divine abilities to keep up." It was clarified the poster meant this for 3.X, 4e, and 5e...
Except we know this isn't true in 5e (and by extension One DnD)
And this is only true in 4e if 1) You consider attacking with Charisma to mean you are bad at fighting while attacking with strength/Dex is good at fighting and 2) You don't mean dealing the most damage (in which case the strikers like the Rogue, Ranger, and Barbarian are the best)
And it is only true in 3.5 if you don't decide to use your feat options to become a generalist weapon user (a choice you can make) AND you don't use your normal feats everyone gets to take non-combat feats (a choice you can make)
So, all in all... I find this to be a really weak claim. It is more accurate to say an OPTIMIZED fighter, in 3.5 only, is better in combat than a Paladin.