On natures: Either will actually do, though Modest is the most recommended nature.
On abilities: Flash Fire. Early Bird won't actually be of much use to you if you go for one of the standard 'doom sets.
Anyway, be warned that the Solarbeam set will leave you with a hole in the moveset that's normally taken up by Sunny Day. Switching in Houndoom might be a bit risky, given its defenses, so you can either leave SD in or have Groudon set up a courtesy Sub before switching in Houndoom to Solarbeam your opponent into OMGWHATWASTHATville. The other moves in Houndoom's set (i.e. other than Sunny Day and Solarbeam) Fire Blast/Flamethrower and HP Ice/Crunch. Top it off with Leftovers, and you're good to go.
The alternate, if you're interested, goes like this:
@ Leftovers
- Flamethrower/Fire Blast
- HP Grass/Pursuit
- Will-o-Wisp/Beat Up
- Crunch
And if you don't like working with Houndoom, there's another good Fire-type in Ninetales. It doesn't quite have the firepower (excuse the pun) that Houndoom packs, but it's been known to survive Surf -- which is something for a Fire-type.
The standard set for Ninetales looks a little like this:
Timid Ninetales @ Leftovers
- Flamethrower/Fire Blast
- Will-o-Wisp
- HP Grass/Grudge
- Protect/Substitute/Confuse Ray/Safeguard/Overheat
Sorry for the erraticness of the above sets. It's more like a "choose one of the above" deals.
Hope that helps a little. Good luck!