Centiskorch (Sizzlipede), Coalossal (Rolycoly), and Flareon (Eevee) are good choices, and they're all available pretty early. They have good stats: Coalossal being a good tank, with high HP and Attack/Defense stats, and a decent Ability in Steam Engine to help its Speed problem. Flareon is a good sweeper with really good Attack and pretty good Speed, plus with Flash Fire it can potentially get even stronger. Centiskorch has good stats all around, surprisingly not that many weaknesses for a Bug type, and again, a good ability in White Smoke. It can also learn Power Whip and Solar Beam for coverage, with Coalossal having Ground moves, Solar Beam, and Rock moves available to cover itself and others.
Since you're having trouble getting an Eevee, I'd suggest Heatmor instead. It's first obtainable on Route 6, and has good attacking stats (not as good as Flareon's Attack stat, but still.) It has average of everything else, and a really diverse movepool. Plus, thanks to it having both good Attack and Special Attack, you don't have to worry about which type of move it is and can allow it to be a mixed attacker. It has the same typing as Flareon, so no worries there. It also has Flash Fire just like Flareon.
Turtonator's a good Pokemon for your last member, but it is pretty late game, in the Lake of Outrage.
As for Fire Stones for Vulpix, and if you do find an Eevee there's one in Motosoke Riverbank uphill up against the wall of Motostoke, and a bit later, in the Potbottom Desert if you bought Isle of Armor.
See here for other locations: https://serebii.net/itemdex/firestone.shtml
Source: this site, Pokemon pages and such.