Yeah, I now Paladin's don't have alignment restrictions now, but none of the starting paladin subclasses right now feel really appropriate for an evil character. Consider that you can be a Lolthsworn or Githyanki paladin, with dialogue options implying faithfulness to Lolth/Vlaakith...how does that even work from a roleplay perspective? Ah yes, paladin of Lolth, defender of the innocent...?
Even Vengence doesn't seem like a perfect fit unless Larian really reflavours it.