What's the difference between the Battle Frontier and the Battle Maison/Tree? I skipped generations 2-5 so I don't have a clue.
Reading Bulbapedia's article would get you a better idea:
Gen III's and
Gen IV's (the only two generations with a Battle Frontier).
To give a quick summary, the Battle Frontier is an extension of the Battle Tower. There's now multiple "Battle Facilities", Battle Tower just being one of them which does the basic Single & Double battles (and in later generations gets replaced with the Battle Subway (Gen V), Battle Maison (Gen VI), and now Battle Tree (VII)). Other Facilities have gimmicks to them, either how you progress through the Facility or effecting the battles. Here's a quick rundown of each Facility of their gimmick (skipping the Battle Tower since we all know that):
Gen III's Emerald was the first game to introduce the concept of the Battle Frontier and had 7 facilities:
Battle Palace: You don't command your Pokemon, instead your Pokemon chooses its own moves depending on its Nature. Some Natures are more aggressive, some more tactical, and if they get to half HP they switch what moves they use.
Battle Factory: Instead of using your Pokemon, you use rental Pokemon. As you battle through, you get to switch one rental Pokemon with each opponent you beat (though you only know the Pokemon species when trading so during battle you got to pay attention to what moves and Ability their Pokemon ma have had).
Battle Pyramid: This is a dungeon crawler, though you can't use your items. Instead your given a smaller item pack where you can store items you find (or a Pokemon who knows Pickup finds) in the Pyramid as you travel through and up it.
Battle Dome: It's a simple bracket tournament.
Battle Arena: You only get to use three moves. If both Pokemon are still standing after those three turns, your and your opponent's Pokemon are than judged how well they did in three categories: Mind (how well did they choose their offensive attacks), Skill (how well was their accuracy), and Body (how much HP they have left). The loser of this decision is than knocked out and goes to the next match until one of the trainer wins.
Battle Pike: You travel through a series of hallways, given vague hints whether there's a trainer, something good, something bad, or nothing down there.
Gen IV had their Battle Frontier in both Platinum and the Gen II Remakes, HeartGold & SoulSilver. They were both the exact same and only have 5 Facilities this time:
Battle Factory: Makes a return (but run by a different Frontier Brain, I'll explain later) and does the exact same thing as it did for the Gen III iteration. It's the only returning Battle Facility other than the Battle Tower.
Battle Arcade: Before each battle a 4x4 tile screen goes through a roulette cycle. Each tile would effect the battle in a certain way (good or bad) and may only effect the player, challenger, or both.
Battle Castle: Normal battles, but after each battle you get "Castle Points". Your Pokemon are not healed up after Battles, instead you must can use Castle Points to either heal your Pokemon, buy items, or a few other services to help you in your next battle.
Battle Hall: You can only enter with one Pokemon. Before battle you get to choose what type of Pokemon you want to battle next, but choose carefully as you're only picking one of the types of the Pokemon will have (the other type can be anything and will choose types either super effective, resistant, or immune to your Pokemon's type).
Finally each Facility is ran by a "Frontier Brain". After a long row of streaks you'll get to battle the Frontier Brain and if you win you get a Badge-like award to show you beat them:
Gen III gives you "
Symbols" which look like a Badge though are more simple in design (just a plain circle with a symbol representing the Facility on it). It comes in two colors: Silver (first time beating the Frontier Brain) and Gold (second time after attaining a longer streak than before).
Gen IV gives you "
Prints" which are rectangle photographs. It shows the Battle Facility in the Background with the Frontier Brain's and playable character's overworld sprite on either side of it. There's two versions: Black & White (first time beating the Frontier Brain) and Colored (second time after attaining a longer streak than before).
And as always you get Battle Points to spend on BP shops. There's also additional areas to visit in the Battle Frontier.