Fire stones-Johto: National Park (Come 1st in Bug Catching Contest), Route 36 (PokéGear Phonecall)
Kanto: Route 25 (Show Bill's Grandfather a Growlithe in HG or Vulpix in SS)
Vulpix is another very easy obtainable fire type, but there are not many more.
But Ponyta is a good bet in this link it has its locations.