If you can get hold of it, the OOP 3.0 supplement "Noble Steeds" can do wonders for this problem. PCs can invest x.p. in horses (or camels, mules, etc.) and advance them as destriers, palfreys, or coursers. Destrier is a warhorse, but you can improve them over the base; coursers are fast horses; palfreys are riding horses. They have different class features and feats, and unusual mounts get access to unusual feats. Having spent x.p., the player becomes eager to protect the mount with protective gear. This has worked so well in my campaign that one player wants to introduce a similar system for his dog.
Even if you can't get the supplement, introducing some sort of mechanic to make mounts more survivable can make for a richer game if you're surface-based rather than dungeon-based. Mounted parties are faster and more maneuverable, can carry more gear, can see farther, and have less chance of being surprised than parties that travel on foot. At higher levels, when the spellcasters normally start overshadowing the fighters, a knight with a properly equipped and trained mount will still be pulling his own weight.
As for the paladin - the special mount can't be called until 5th level. The special mount is usually a heavy warhorse - which means that, at the DM's discretion, it can be something more exotic. A player who equips his paladin with a mundane warhorse, tricked out with feats, as soon as he can afford the horse, and waits past fifth level to call his special mount, can justifiably be given something a little fancier when he finally decides the need is great enough to call the mount. Pegasi and hippogriffs are cool enough for anybody, and will allow him to keep up with the wizard who insists on flying all the time in combat, pursue the fleeing dragon, and do aerial recon of enemy forces.