Well to provide some semblance of comfort about the non-good paladin options, the oath of the avenger subclass (which I had really hoped would be included in the patch) is the phb oath meant to allow for that. It's the "defeat your enemy by any means necessary" paladin, very ends justify the means in their approach. I'm guessing they weren't included in the patch because they wanted the oathbreaker to be the "evil" option for EA.
As for paladins and deities, ever since pillars of eternity I really like the idea of paladins gaining their power through devotion to ideals rather than gods, but the option to tie paladins to gods probably would have been nice for role-playing purposes. Maybe they could make it an option depending on the oath you choose. So you pick the oath, and then you have the option to pick a god who would line up with the oath so you can roleplay as a paladin of them specifically.
Also I think every class getting to have a deity could be cool. Wotr pulled that off to awesome effect. I'll never forget when my dwarven monk who worshipped Torag was blessed with stone skin during an early set piece combat. Nor the little nods to your deity that cropped up.
