How do you figure?
Both are proficient with all armors, all shields, and all weapons.
Lv 1 -> Both get +1 BAB and +2 Fort
LV 5 -> Both get +5 BAB, +4 Fort, +1 Ref, +1 Will
LV 11 -> Both get +11/+6/+1 BAB, +7 Fort, +3 Ref, +3 Will
Level 18 -> Both get +18/+13/+8/+3 BAB, +11 Fort, +6 Ref, +6 Will
Where is the fighter outperforming the Paladin? They seem to have the exact same pure combat stats. So where is this idea coming from that Paladins can only keep up by using Divine Features?
At level 5, the 3.5e fighter has three additional feats over the paladin. These can be used for things like Power Attack and the fighter-exclusive Weapon Specialization, or possibly getting access to swanky exotic weapons.
The paladin has Smite Evil 2/day, +Cha to all saves, Lay on Hands for level x Cha hp of healing per day, immunity to fear and give nearby allies +4 to saves vs fear, immunity to disease, a low-power version of Turn Undead, and possibly a 1st-level spell per day (depending on Wis).
The paladin also has way more MAD than the fighter. The fighter wants high Strength and Constitution, and ideally an OK Dexterity to max the benefits of full plate and decent Intelligence to unlock the fairly sweet feats with Combat Expertise as a prerequisite (e.g. Improved Trip). The paladin wants the same Strength, Constitution, and Dexterity, but also need Charisma for their special abilities and a little bit of Wisdom for their spells.
The problem for the fighter is that feats are a fairly flat progression. At 5th level, the fighter probably has the edge on the paladin in an actual fight, since most of the paladin's special abilities would be irrelevant and the fighter probably has +1 AC (Dodge) and +2 damage (Weapon spec) over the paladin, and possibly access to shenanigans like Improved Trip. But there are very few feats with higher prerequisites than (effectively) 6th level. You have the continuation of the Weapon Specialization chain with Greater Weapon Focus at 8th and Greater Weapon Spec at 12th, Improved Critical at 8th, and there's Greater Two-Weapon Fighting and Improved Precise Shot at 11th. Oh, and technically Stunning Fist at 8th. But other than those, there's really nothing new happening for the fighter – they get bigger numbers, and if they have the stats for it they can expand into other feat chains, but there's nothing exciting happening. Admittedly paladins don't get much excitement either after 6th level, but they at least get access to higher-level spells.
Both classes get significantly better with more splatbook access. Partially because they offer prestige classes you can take instead of the lackluster high-level benefits these classes offer, and because they offer alternate options. Fighters get way more options for their feats, including some that are actually pretty fun, and paladins get divine feats they can take to actually get some use out of their otherwise useless Turn Undead attempts.