I don't agree with you there. Classes as a whole, with talents and glyps included, are balanced against one another (or at least should be). It doesn't matter if class 1 has a built-in movement boost, and class 2 has to pick between 3 movement speed boost talents. They both end up with a movement speed boost. Class 1 might very well have a different row of talents that class 2 has built in, or is balanced around not having.
It is entirely arguable - I don't even disagree with your analysis, it is to compensate for something baseline in others and they may have talents to compensate for something baseline the move-speed-talent-folks already have. Mostly it's a scope thing.
If it was an isolated situation, I would not put forward my argument. However, when at least 1/2 of all classes have a movement-speed-increasing talent (most of those an entire tier), then I see systemic issue. One class would be flavour. Half your classes is balance correction. Reference all the tank homogenization they've felt necessary over the years (taunts, interrupts, threat modifiers, etc) in order to correct balance issues.
Additionally it overrides boot enchants. Movement Speed on boots provides 7.5% speed increase which does not stack with things such as Feline Swiftness or Pursuit of Justice. So now movement talents must balance against another class buffed by an enchant. Either the talents balance against un-enchanted other classes, which means other classes gain an advantage once enchanted, or the talents balance against enchanted other classes, which means other classes are at a disadvantage unless enchanted.
It's entirely possible the movement talents put those classes to a relative advantage over classes without such talents. It's not intended as a "buff us" argument, but as a "something is seriously flawed, not necessarily us, and we've had band aids for 2 years" argument.
On more productive topic:
If Devo Aura is dropped (seems likely), then paladins lose the last vestige of the aura system. Auras being such a core flavour item of the Vanilla paladin, that seems to be prime material for generating a new talent (or tier). Either CD (I could see Prot with something akin to a priest barrier or deathknight AMZ) or passive (effect X for us, and effect Y for everyone within 40 yds, where Y joins ranks with some other existing no-stack group buff).
The changes all seem rather straightforward, even streamlining. Past X-pacs have seen many/most/all(?) classes with changing, evolving, or replacing abilities (Paladin examples include: Divine Storm, Templar's Verdict, Holy Power, Inquisition). Barring values changes on every ability, there appears to be little to no actual gameplay change. Again, ignoring value changes (more/less damage on ability A, CD tweak on ability B, or Draenic Perks), it's almost the change level of a tier patch.