Battle Maison is a whole other beast compared to the main story. It's easier to craft a team for the Maison
after you've beaten the main story, when you have everything available to you for EV training/breeding/move tutors/DexNav/items/etc.
As far as in-game goes, you'll need a Water type--it's Hoenn, it has a lot of water, and a Water type is good to have vs Team Magma. There's a bunch to choose from, but some decent early game ones would be like Wingull or Azurill or Magikarp (y'know, for Gyarados). You can fish up a Carvanha or a Tentacool around the time you need Surf to continue on. If you're willing to wait late into the game, there is Spheal as well.
Speed Boost (Mega) Blaziken is a good 'mon tho and you can use it in the Maison when you get to that. Fire/Fighting is a good offensive STAB combination, and together with Speed Boost makes for a potent sweeper. You'll kind of want to aim for a set like this when you're finally gearing up for the Maison:
Blaziken @Blazikenite
Ability: Speed Boost (retains this upon mega evolution)
EVs: 252 Atk / 252 Spe / 4 Def
Nature: Adamant
-Flare Blitz/Fire Punch
-High Jump Kick/Low Kick
-Protect
-Stone Edge
There are some Pokemon that Blaziken will have difficutly handling (or is outright checked/countered by), which off the top of my head is like Landorus-Therian, Azumarill, Salamence, Lati@s, and Talonflame. The Maison will throw these at you eventually, so you need to be prepared for them. Fortunately a bulky Water type with an Ice coverage move handles all of these fairly well bar Azumarill.
I definitely recommend getting a Deerling on Route 117 when you reach that part of the game
Or I can trade ya one in about 8 hours
Just a note on this bit, while you will get to route 117 early-ish in the game, Deerling is only available via the DexNav, and even then only until after you have dealt with the box legendary.
