@OP,
I’m in a similar boat - been maining Warrior since Cata/MoP but eventually transitioned to Ret/Prot Paladin.
The obvious bonus of a Paladin is that they are one of few classes that can fulfil all three roles (Tank, Healer, DPS), so even if a particular spec falls out of favour, you can consider any other role if you wish to remain on that character regardless. All three specs are exceptionally sustainable and thus have absolutely no issue with any solo content (or even solo’ing group content). It is the character I go to when I want to farm transmogs and my main character (Ret) for Mythic+ and Raids.
The joy of RetPaladin (especially Mythic+) is that they are an absolute menace vs AoE situations, especially with certain traits (but still huge without them). This means they’re fantastic at getting you to bosses in a hurry through all the trash. While their ST DPS isn’t nearly as good as their AoE potential, it is still very consistent and not too shabby, plus they have a wealth of utility - a lot of which can be very, very useful against almost every M+ affix.
DK’s, on other hand, are in a decent spot but are limited to two roles and said specs are either a bit convoluted or, in another case, a bit dull.
You seem to enjoy the lore, in which case DK certainly has an advantage, but if gameplay beats lore in your mind, then I thoroughly recommend going Paladin.
As for PvP, Ret is the type of spec that ‘blows up or get blown up’, so some may find that good/bad. However, I prefer to PvP as Protection. You have decent duelling potential due to being very sustainable, but your strength is not in kills - rather, your utility and extremely annoying playstyle. Knocking people about with your charger, high healing-done despite being a tank, interrupts, slows and other shenanigans can make BG’s quite fun. There was also a time that Prot Paladin was quite common in arena as more of a full-healer (just super tanky). However, Holy Paladin in and of itself is perfectly viable as well.
If you truly want to try something other than your Warrior, then I wager Paladin would be the closest thing for you.