I ran into a similar problem with a campaign I was working on. My intent was to replace common domesticated animals with domesticated versions of fantastic animals. No horses, but there are sleek, long-legged reptilian creatures with fast land and swim speeds (and stats otherwise very similar to the Light Horse) called Riverwolves which people could ride instead. This worked out OK. But replacing Oxen with massive, iron-hard turtles called Ferrouks was a mistake...all of a sudden Joe Dirt-framer is plowing his fields with something much tougher than a 3rd-level fighter. When you can resolve the invasion of the Orcish horde by opening the stable gates and letting your livestock kill them all, what's the purpose of having a story about an orcish invasion in the first place? The entire setting became all about the critters, and it required a ton of supplemental rule-changes to try to make it work.
That's the same problem you'll run into by replacing horses with Firemares...that's a powerful critter that can be had by a low-level adventurer for little cost (if you make them cost what they're worth, based on their abilities, they are no longer able to replace horses in the game world's ecomony).
Ultimately, I left my cool critters in the setting, but relented and re-introduced the "common" animals (horses, cows, etc). The fantastic domesticated animals became rarer, and harder to obtain. Another key to making this kind of thing work is being careful with names. If you call your elephant-analogue creature a Rock Titan, players get what you want the creature to be, without bashing them over the head with he exposition-stick. Call it a Phaelroph, and you will be explaining yourself over and over, since the name itself means nothing.