I always find Maikarp-type Monsters the most fun. Ralts, Trapinch (for the love of god though do not evolve it into Vibrava until level 44), Mawile (wait, can you even get that Mega Evo in the main game?) and Corphish (though he gets good pretty early now) are all some of my favorites that pull their weight in the late game.
As far as something that's viable the whole time, I'd recommend the Aron family. Great defenses and Solid attack. While you have to get its levels up to speed (It starts 10 levels behind, sadly), once you do so it's an extremely dependable party member, and it learns fairly decent moves and TMs early on. Aggronite is also found as soon as you go to Rustboro tunnel and break the path open with Rock Smash, so you can bust out Mega Aggron as soon as you hit level 42.
I've been wrecking face with Megaggron ever since Fortree.
Marcargo is cool, but holy shit at the weaknesses. Probably the most appealing thing about Marcargo is having access to Recover. I used it in the original RSE to okay effect.
Ninetails is the best out of these 3 if you DexNav it's HA. Fire off those sunboosted Flamethrowers and Solarbeams! It's movepool is barren as hell though.
Yup, Ninetales is the Fire-type MVP (not including Blaziken of course) by a long shot.