I'll be honest, Pointy Hat lost me by saying the old-school LG Paladins made role-playing predictable and tedious. As someone who started playing paladins forty years ago, I can say that they have never been necessarily predictable or tedious. They're like the role-playing equivalent of a sonnet; they're a chance to express creativity through the focus of limitations.
It will be interesting to see how they implement 5E paladins in the full game as the tabletop version turned me almost completely off what had been my favorite class. I think part of the problem for me is that while more player choice is a great thing, the increased freedom changes the nature of the game. Some of the changes work really well, others remove some of my favorite aspects of a character type.
I dunno, in 2e, it felt like cheating at cards would get you kicked out of your order.
I like the idea that you can bind yourself to different oaths with different restrictions. e.g. An oath of vengeance pally may be willing to burn down a small forest to flush out a group of bugbears, while and oath of the ancients pally would see that same act as an atrocity.
