For me the bottom line is: Paladins are balanced by their need to have both Str (or Dex for the nutjobs out there) and Cha, thus splitting their focus. You are balancing your offense and support capabilities when picking up an ASI. A 1 level dip into Hexblade breaks that balance and turns Paladins from a really strong class into a broken class. A +5 to hit/damage and to all your (and your close friends) saving throws by level 9 is miles beyond what any other class can pull off at that stage in their adventures.
If it was just swords bards that were doing it, then whatever. It is a decent enough subclass, but it wouldn't push it into broken AF in the same way.
You're forgetting one: Constitution. They go down fast without it. Paladins are almost as MAD as monks are, but at least monks can use Dex for attacks and AC. And Paladins don't get enough spell slots to make smite a consistent damage dealer, and they don't get as many weapon attacks as fighters. Having a hexblade dip doesn't exactly break them, especially when rogues are outright busted with their two bonus action shoves.
