My Sword Coast Adventurer's Guide says that in FR all paladins have a patron deity granting them divine power. It then goes on to say that most paladins are devoted to a particular deity, leaving open the possibility of some having several or none. That doesn't necessarily refute the statement that it still takes a deity somewhere to grant divine power, but it also leaves open the possibility of a direct connection to the divine.
No idea what previous source books say, but the PHB is a sourcebook too and it's legit to have its lore take precedence.
Personally, in a world with music-magic, I'm perfectly fine with oath-sworn tapping the divine directly. So if Larian lets paladins choose a deity or opt none, it's all within reason imo.
