"The Cleric can do everything a Paladin can do."
Yeah, I think as usual, the problem with the paladin is the cleric more than the fighter, at least from what we can see of the classes so far.
The battle cleric has all armor proficiencies, one martial weapon proficiency (deity's favored weapon?), spells and channel divinity.
The classic paladins should probably have channel divinity, probably in reversed order (smite then turn undead) and possibly 'lay on hands' as their own unique version of channel divinity. That covers the divine half pretty easily.
But what about the fighter half. What does the fighter get over the cleric?
+1 attack, +2 damage
~+1 hp per level (assuming the d10 as put forth in the last L&L)
All weapon proficiencies (what is the marginal benefit of additional martial weapons?)
So we can't really give the first line without severely stepping one what little ground the fighter has. But even giving them the other two entirely . . . then we weigh 1hp and a few secondary proficiencies against the cleric's full spellcasting progression. Is it really a reasonable trade?
So we need to find something that represents the paladin himself to counterweight the spellcasting of a cleric. Flatter math has definite benefits when it comes to scaling at higher levels, but it makes it a lot harder to squeeze things in the middle at the lower levels.