I mean,... you guys don't have to like it or agree with it. If it doesn't work for your tables,then that's what's most important... but I'm just quoting to you the relevant passages here, as the basic facts of how it is written in 5e. You don't need a god, as written.
Although many paladins are devoted to gods of good, a paladin’s power comes as much from a commitment to justice itself as it does from a god.
Many, not all or or universally required.
The most important aspect of a paladin character is the nature of his or her holy quest. [...] Are you a glorious champion of the light, cherishing everything beautiful that stands against the shadow, a knight whose oath descends from traditions older than many of the gods? [...]
Paladin following an oath and a creed, not a deity.
How did you experience your call to serve as a paladin? [...] Did another paladin sense the potential within you and decide to train you as a squire? Or did some terrible event — the destruction of your home, perhaps — drive you to your quests? Perhaps you stumbled into a sacred grove or a hidden elven enclave and found yourself called to protect all such refuges of goodness and beauty. Or you might have known from your earliest memories that the paladin’s life was your calling, almost as if you had been sent into the world with that purpose stamped on your soul.
More in-text examples that don't involve deities.
There's a pronounced difference between smiting someone "In Tyr's name" and smiting someone "Because it is just". The difference may not make sense to some people, but it's an important one all the same. Certainly, a Paladin acting justly would be taken as performing acts that honoured Tyr - Tyr would certainly say so, and take that as a source of power happily (and as mentioned, would likely try to sway the paladin to speak their name and follow them directly)... but there's still an important personal difference, which now, in 5e, we are allowed to have and to explore, where previously we were not.
Imagine a situation where Tyr fell; where Tyr was driven to act unjustly and lost control of his folio of justice. The Paladin who devoted themselves to Tyr would either need to follow the new Tyr to continue to receive powers, perhaps being driven to injustice themselves as a result, or they would need to renounce or break their oath and swear a new one if they felt they couldn't follow him any more. A Paladin without a particular deity, sworn to an oath that bade them act justly, uphold the good and to fight injustice and evil wherever they find it, but without a particular god in mind, would NOT be in the same position; they would be unaffected by Tyr's fall.
