Okay, so, about that Paladin. Leaning hard in that direction, and I'm basically committed at this point. I've got two chief concepts, one that I think is a relatively safe bet, and one that's... while I wouldn't call it terrible, I would call it potentially inappropriate tonally for the game if we're going for a classically heroic sort of deal.
First, Oath of Ancients Paladin. Very tanky, if I'm reading the mechanics correctly, and would absolutely fit the bill of a Selunite, Sunite, Tymoran or some member of the Elven pantheon. Joyous, supportive, and a ray of sunshine who understands that life is for the living, and the living gotta live it up. In the meantime, they serve their duty to expunge the horrible things that want to snuff out that light of joy. I imagine them fresh-faced, innocent, and emboldened by tales and songs of great deeds, striking out for the first time to emulate those ancient heroes and to leave their mark on the Realms. This is the safe bet, and I rather fancy it myself as I typically play those with a clearly heroic bent. Then I made a horrible mistake and started reading through the Sword Coast Adventurer's Guide and Xanathar's...
So hear me out: Paladin of Asmodeus, either Oath of Conquest or Oath of Devotion. Hold on! Don't leave yet! Tastefully Evil -- the bargain-striker, the deal-maker, the oath-swearer -- and not so much the stabby-stabby murder-times evil. Honorable, dependable, somewhat selfish and a little deceptive at times to be sure, but with that ever elusive "hidden heart of gold." Somewhat in the same vein as a Warlock I suppose, albeit more divine and martially inclined, having made a pact to save their own skin by striking similar deals with others and spreading the deeds of the Lord of the Ninth (promoting law and stability, removing lesser evils and threats from power, et cetera). Understands not everyone wants to make a deal with the literal devil and obviously won't force the issue (mostly because they probably aren't worth it if they're unreceptive in the first place), but hey, that's the price they paid to avoid an afterlife of centuries in the Fugue, with a solid chance of simply just being damned to the Nine Hells and tormented for eternity anyway. Obviously this requires a little more finesse and tact to be done correctly, and the last thing I'd want to do is step on peoples' toes (or be a bad fit for the party), but I thought it was a neat little idea.