What follows are just my opinions.
First, it depends on what the mounts are. I mean, is the mount a summoned force that takes the shape of a horse, or is it an actual horse imbued with magical energy?
If it's the first, it's a lot easier to rationalize "upgrading" it to a more powerful creature type instead of adding HD. If they're actual creatures, it's a lot less likely that you'll have much choice. Also, you can say that while a Wizard picks his Familiar, the Mount is given by your deity (i.e. the DM) and so you're stuck with what he gives you.
It all pretty much comes down to the DM, though. A warhorse is the baseline; a 4 HD nonintelligent creature with 4 points of Natural Armor, some simple attacks, and a 50' movement. Nothing spectacular.
If you want something substantially better, it's a big jump in power. But I'd leave that to Feats and/or Prestige Classes.
Also, point of confusion: the Natural Armor listed in the PHB doesn't say it's an increase, it just says "this is the natural armor rating". It also says "4", not "+4" (see the Blackguard in the DMG, for him it's "+1"). Per the other rules for named bonuses, I assumed this meant they did NOT stack (use the better of the two), especially since the Heavy Warhorse (the standard Mount) has 4 Natural Armor. After all, the "STR Adj" is listed as a plus, and the INT isn't, so it seems pretty clear that the NA isn't adding.
Does DotF (or the Sage) say the other way? Never really read through that book.