Alternative to Paladins

I like Paladins but they are damned hard to play in games.  Prior to MMOs Paladins were just Fighters with a little something extra, but post MMOs Paladins are some sort of bollixed up holy warrior.  Invariably someone in your group decides to play an evil character and that puts your Paladin in a bind.  While any good aligned character should disdain adventuring with an evil character, for a Paladin this will lead to all sorts of problems such as loss of paladinhood, which puts you at asking why you bothered to play a Paladin in the first place.
Sometimes it is the DM who has it out for your noble warrior.  Which is even worse.
The good news: there is an alternative.
Paladins are knights.  You can argue with me on this but you will be wrong.  You might think Paladins are holy warriors, but they are not and if that is how you feel just fuck right off right now.  The Cleric is a holy warrior.  The Paladin is a knight.  The creative origins of the Paladin trace back to Three Hearts and Three Lions by Poul Anderson.  The Paladin is a good, noble knight and everything about the Paladin through the original D&D, and 1st and 2nd edition AD&D supports this.  The 2nd edition Complete Paladin's Handbook even takes this knight concept to the extreme level stating that Paladins disdain wearing anything but metal armor and no armor that would be considered less than noble (it offered a low AC 7 hauberk as starting armor for poor Paladins that could not afford something better).  It also discusses origins, squires, and all the things that make a knight.
So is it a holy warrior you desire to play or is it a knight?

"Bad day to make fun of the Ranger."

If you want to play a Paladin you should really consider that you should be playing a knight.  The 5th edition offers options for this in the background section.  Indeed the default background for Paladin is Noble.  What does that offer?
Aside from roleplaying guidelines and the two background skills (in this case History and Persuasion) it offers the special ability of being able to claim hospitality from other nobles.  Many backgrounds offer variants and Noble does not disappoint here as it offers the Knight variant.  This background will make your character a knight, the lowest level of nobility and you will get retainers instead of the hospitality feature.  Any class can choose this background, but let's look at the virtues of a Fighter with the Knight background.
As a Fighter you will get the d10 hit die, same as the Paladin, and proficiency with all armors, weapons and shields, same as the Paladin.
Your saves will be Strength and Constitution, unlike the Paladin which has Wisdom and Charisma.
The Paladin starts with two abilities: Divine Sense (formerly Detect Evil) and Lay On Hands (a healing power).
The Fighter starts with Second Wind (self-heal) and a Combat Style.  The Paladin will get a Combat Style at 2nd level.  The Combat Style is where your Fighter Knight really shines.  You could choose Defense and get a +1 AC, or Protection and use your shield to guard your squishier friends.  You could choose Great Weapon style and gain bonus damage with two-hand weapons if you like.  I won't list them all here, but you have options.
At 3rd level the Fighter selects a Martial Archetype to follow from this short list:
Champion-specializes in doing damage and surviving.
Battle Master-specializes in being a battlefield strategist and gains maneuvers.
Eldritch Knight-learns some magic spells (avoid this, although the Paladin will be casting clerical spells by that time, it's anathema to the Knight concept).
The choice is yours, but Battle Master is an attractive option for the noble leader type, which a good knight should be.
As you play and gain loot you should be able to get a horse, at which point your knight really starts to seem like a knight, since knights are a cavalry component and tend to run roughshod over the infantry in battle.  At one time, long ago, before the MMO nightmare settled into the "norm", the Paladin called for his warhorse, a special mount that was his and his alone, bonded in a sacred rite.  Well those days are over, friends.  But a knight needs a horse.  It's practically part of the job description.

THIS is what knights do.  Note the conspicuous horsey.

So our take away for this lesson is the Fighter with the Noble background Knight variant is the new Paladin because it is the old Paladin as it was meant to be.  There are benefits to being a regular Fighter such as no loss of Paladin status due to a some asshole DM's personal Kobayashi Maru designed solely to fuck your Pally in his metal-plated arse, freedom to retain wealth, and some pretty nice combat abilities as you gain in levels.  Certainly you don't get the Pally's freebies like Lay On Hands or Immunity to Disease but also you don't have to worry about a handful of spells and who really needs to turn undead anyway?  That's the Cleric's job.  Give it a try, former Paladin brothers.  Use strength of character and strength of arms instead of relying on supernatural powers and see if it doesn't suit you right down to your sabatons.