I don't think that paladins should ever have been tied to any alignment in the first place. Make them warriors devoted to a particular god, and let the god sort out what they are supposed to do and how they are supposed to act.
5e does this to some extent with their sacred oaths, and it is (IMO of course) a big improvement.
