I decided, since this topic keeps coming up, to go back through the edition handbooks I have and actually check Paladin's deity-requiring status. Because I was sure that paladin never actually required a deity, and people were thinking of divine champions, which definitely do require a patron deity.
This is what I found: Paladins have never been required to have a patron deity, going back to 2e. They dedicate themselves to the forces of good and law and divine power is granted via your dedication to these principals (in the same way a druid gets power from dedication to nature, but not worship of gods or spirits). Paladins can be and often are also devout members of their churches, but it isn't specifically their devoutness that gives them powers.
But that's exactly the point people are making. Sure, they aren't required to follow a deity. But they have always had that option available to them. And in the vast majority of stories coming out of the Forgotten Realms setting at least (this is a setting-specific point), paladins have followed a deity and have been treated as holy warriors.
