The Thayan Menace said:
...I know it's a cliché, but true respect is earned ... not given.
-Samir
I respectfully inform you of your wrongness.
A paladin has
earned automatic respect the day they became a paladin, not when you say they do. Paladins get this respect at 0 xp, right out the gate.
To make a real-world parallel, in D&D-land a paladin is like a priest and a police officer combined. Or a rabbi and a firefighter. Personally, I don't need such people to "earn" my respect. I automatically respect them for their occupation in life.
The paladin is a tool of her god. She has sacrificed her Free Will to help people, even to the point of sacrificing her life if need be. In D&D-land, that garners automatic respect from other PCs, peasants, merchants and so forth. This is not difficult to imagine.
You chose to run a CN character who can change his behavior whenever it suits him, so naturally your PC must "earn" respect. The paladin, however, deserves respect from everybody.
Evil people and self-centered jerks are exceptions, of course; so, yes, if you are roleplaying a self-centered jerk, then yes, you can withold your PC's respect for a paladin.
Nonetheless, the paladin still
deserves respect, up until the moment they lose their paladinhood.
Tony M