I've recently written an article for a french webzine on this subject.
It's an house-rule that give a 5th level paladin the opportunity to choose between a mount, an armour, a weapon, a symbol or a animal companion. It is an emblem of the Paladin Status.
The Mount Emblem is the same as the mount in PHB, and I made up a progression for each of the other Emblem.
This idea came out because the campaign setting we're talking about in the webzine is a ocean setting. A lot of paladin are spending more time aboard than on lands and mounts were clearly not as useful as they could be.