When a priest casts a spell, there should be some doubt as to whether there was any magical involved, or whether it was just a coincidence.
No offense, but healing all injuries is not coincidental. That's about as obviously magical as you can get. Giant gaping wound there one second, and gone the next. Calling down angels and spirit weapons is a traditional power, and that's very flashy. Hells, Flame Strike has always been around, at least from AD&D, and tha'ts as cleric-y as you can get. Same as something as simple as a light spell - very flashy, traditionally a cleric spell. Same with Druids. AD&D, first edition, Entangle and Faerie Fire. Both highly flashy spells that, in no way, can be considered to raise doubt that its magic. Plant Growth is one of my favorites, because you can instantly create a jungle from almost nothing. Or, as I have my druids do, help crops grow successfully overnight for pastural communities.
I think you're confusing the source material difficulty of proof in reality with what the game intends. Something based on Christian-style miracle workers and "pagan / heathen" faiths are going to be less flashy by nature, sicne direct evidence of divine beings is scarce in reality, whereas the wizard, based on things like alchemists who produced explosives, are going to be flashier, since explosives are real and naturally flashy. But that doesn't imply that clerics and druids are intended to be subtle and doubtful in D&D - its just happenstance based on the source material. There's no such theme built into the game, no matter how far back one looks.
Well, compare the 2nd level Paladin spells that all paladins get:
Aid
Branding Smite
Find Steed
Lesser Restoration
Locate Object
Magic Weapon
Protection from Poison
Zone of Truth
and then some paladins get Misty Step. One of these things is not like the others... Hrm, healing, smiting, finding the truth, and ... short range teleporting.
Yes, lets analyze this, shall we? The general paladin spells are based on things like smites, healing, detecting things and auras. Which are also all innate abilities of the paladin - channel divinity, smites, lay on hands, and the aura. The Steed is a bit of a nod to the Mount ability of editions past. Its almost like the core paladin spells are based around innate paladin abilities.
Now, out of the four core paladin subclasses (including Oathbreaker), two get Mysty Step. Lets analyze those two. First up, Oath of Vengence. The Avenger also gets Hunter's Mark (with tracking), bane, hold person, haste, dimension door, hold monster, scry as spells. Lots of abilites to find and keep pace with enemies. Lots of ones to keep them from running away. Channel Divinity abilities include inflicting fear to prevent movement and advantage on attacks. Level 7's Relentless Avenger includes movement bonuses. There's no way around it - the Vengence subclass is heavily focused around movement based abilities - both restraining enemies and enabling on the PC's part. This also matches how a number of abilities with the Oath of Vengence's predecessors, both the Avenger 3e prestige class and 4e divine striker class, worked. And, yes, given the naming scheme of both the class and its abilities, its clear there's a definite link between the two. All in all, there's no strong argument that teleportation doesn't work with the Avenger, given their nature. Pursuit of enemies is pretty much their entire gig.
So, Oath of Ancients. A nature- and elf-themed knight type. So, lets stop there for a minute and think - any associations you might have to stereotypical paladins needs to be revised. That said? The rest of spells are all druid in theme (including the only other movement spell, Tree Stride). Abilities include channel-divinity version of Entangle, abjuring fey creatures, resisting magic, and just not dying right. The capstone of Elder Champion is very much "avatar of nature." So, all in all, I do have to agree that Misty Step probably isn't appropriate here. My only guess is that, as much as a number of people hate the idea of blink elves, it exists. It shows up with other fey-themed classes, including bards and archfey warlocks. This is another one. It doesn't quite fit, since the subclass is almost entirely druidic and very little in the way of charms, illusions and other fey-abilities that the bard and archfey patron are renowned for. Something like Spike Growth or Warding Wind would probably be more appropriate. Now, if this paladin had been more themed around "enchanter" style magics, I would argue for the teleport powers.
So, in the end, I agree that Ancients probably shouldn't have misty step here. That said, I still maintain its a shoe-in for Vengence, both historically and thematically.
Without judging, the 5e take on 'pets' seems very video gamey, designed to make them as much as a non-hassle as they possibly could, to the point that the spell effect is so bland it invites everyone to ignore it. (Q: But where does the Paladin's steed go when we enter the dungeon? A: Away.)
I still remember the change from 3e to 3.5 when that change happened. It felt very janky, having a summon horse spell, but it was also far more useful, because the horse got in the way far too often. For good or ill, summoning the horse became standard because otherwise it got in the way of the game in the minds of lots of people. I personally still prefer the flesh and blood animal, but different strokes and all, I guess.
But like others have said, Find Steed is really just a "paladins had horses in previous games, but we don't want to make it a focus" add on. The fact its a summon or not should in, no way, impact the existance of movement-based magic with the paladin. The spell resonates with a different part of being a paladin (mounted knight).
) - makes more sense to my sensibilities than Misty Step or Dimension Door. 
