I'll be quick since the homework beckons me.
I'll make a case for fighting: because it's supereffective against normal. We can continue the trend by making the next gym leader have a type advantage over the previous one to give us a little trend going.
EG: A hypothetical scenario would be like this:
Gym 1: Normal
Gym 2: Fighting
Gym 3: Psychic
Gym 4: Dark
Gym 5: Fairy
Gym 6: Steel
Gym 7: Fire
Gym 8: Water
That is all.
I really like this; it adds this sense of "I'm better than the last guy" in a very visual manner. Perhaps not the same order/choices, but the concept is sound.
To that end, I'd much prefer Excadrill in the 5th or 6th gym, or at least close to it, just because EVs scale better at level 65-70 than they do at 30-35 due to how the growth algorithm works. It makes the entire strategy more threatening, and befits the learning curve of this game.
Also because Gustav is love, Gustav is life.
I suppose it'd be the same theme if he was swimming in lava by his lonesome, but Fighting is easy to be threatening with early due to the massive distribution of moves like Mach Punch, Superpower and Focus Blast. It prepares you to face raw power, which is represented in a heavier form further down the line via a Steel/Ground Gym. Key word here is *prepare*. Using Ground and/or Sand strategies this early doesn't give us the opportunity to teach as much as we could if it were introduced in a Gym later, where its effect is more pronounced. By this, I mean we have a better opportunity to give the Gym Leader a more synergistic team later down the road (better levels, better moves, etc etc), especially for a type as ubiquitous as Ground.
Fighting-types and Fighting attacks have users that can pull their weight early on (level 30-35) such as Timburr/Conkeldurr, Infernape, Hawlucha - heck, even things like Staraptor.