Giant Strider? Monsters of Faerun, Has fire immunity, and fire healing... and fire subtype... and fireballs. 40ft movement speed doesn't hurt either.
Fireball (Su): Twice per hour, a giant strider can emit a small fireball from ducts near its eyes. Each fireball has a range of 60 feet and a burst radius of 10 feet. Creatures caught by the blast must make a Reflex save (DC 14) or take 1d6 points of damage. A successful save negates all damage.
It has a low DC and doesn't seem to scale but it's twice an hour and it's
SUFire Subtype (Ex): Fire immunity, double damage from cold except on a successful save.
Get immunity to cold asap from a spell?
Healing from Fire (Ex): Not only do giant striders take no damage from fire, they are healed by it. Once during each 3 rounds that a strider is exposed to intense heat or flame, the creature gains the benefit of a cure light wounds spell (1d8+1 hp healed). A fireball spell or other intense, fiery attack fully heals the creature instantly.
Depending on your reading, this plus the fireball (su) could result in a full hp heal twice an hour. Even on a bad reading, make a campfire...stick your hand in it...free healing and use your fireballs as cure light wounds.
Resistant to Magic (Ex): Giant striders gain a +2 bonus on all saving throws against magical effects
Nice little bonus.
It has 6 natural armour and a 1d8 damage kick too.
Not bad for a 2HD creature.