3. ASI's are at such a premium for Paladins that playing anything other than a Variant Human will render you a shackled runner, since you will have almost zero room to round out your build with some of the best feats in the game.
4th level variant human: +1 to two stats, +2 to a stat, 1 feat
4th level half-elf. +1 to two stats, +2 chr, 1 feat.
Looks pretty even if you would want to boost Chr as a paladin. Oh, but half elves also get darkvision, fey ancestry and two extra skills.
4th level variant human: +1 to two stats, +2 to a stat, 1 feat
4th level dragonborn: +2 str, +1 chr, 1 feat
So Dragonborn start 1 ability boost behind, but also gets a breath weapon (hordes being somethign paladins aren't good with) and damage resistance.
4th level variant human: +1 to two stats, +2 to a stat, 1 feat
4th level human: +1 to six stats, 1 feat
Not saying "+6 is better than +2", but as you pointed out paladins are MAD. At least three of those are good (Str/Dex, Con and Chr) and Wis is not bad. Plus dex if you're a str paladin for init and reflex saves. All in all, different but not weaker.
This is just three, there's a lot of viable paladin races. They are MAD, but that does make races that get more than +2 total racial ability bumps quite interesting.