Battle: Gym Leader Clay (3960 poke, Quake Badge, TM78 Bulldoze)
Opponent: Krokorok Lv 31, Sandslash Lv 31, Excadrill Lv 33 (Sitrus Berry)

Clay follows in the Unova tradition of gym leaders being several levels more powerful than anyone that shows up in their gyms and a good five or more levels beyond even the wild pokemon in their vicinity.  This makes him exceptionally dangerous with his high-offense pokemon.  The best defenses against the team he has are levitating things that resist Normal attacks (nothing, so far) and fast pokemon with high Special attack- while Sandslash boasts high Defense, all three of Clay's pokemon are weak in the Special Defense.  Krokorok will often put a crimp in plans to use overwhelming physical might thanks to its Intimidate ability, and stacking that with Sandslash's physical toughness makes for a hard road there.  Similarly, while Sandslash's speed is poor, Krokorok is plenty quick, as is Excadrill, and the latter has its Steel typing adding resistance to a number of attacks that would otherwise be viable.  Since you're likely to have a team around level 29-31 at this point, you likely won't have the defenses on hand to blunt this assault.  That means that a quick offense on your part makes more sense in the end.  Be wary of Sandslash's Crush Claw, and while it may take a bit of time to get going, it does have Fury Cutter to give it a little bite against Grass pokemon.  Excadrill packs Rock Slide and Hone Claws, so be wary with your Flying types as well, despite their immunity to Ground attacks.

Once you manage to surpass Clay, he comments on the number of young, powerful people passing through lately and then forks over the badge and TM78- Bulldoze.  Bulldoze is an interesting Ground-type attack that lacks Earthquake's raw power, but has traded about half the power in for the near-certainty of reducing the speed of anything it hits.  Usually, you'd rather have Earthquake's overall strength, but until you can pick that up Bulldoze will fill the spot on your pokemon's movesets quite nicely.  It's also available to a number of things that can't learn Earthquake to begin with, so it can help patch up your coverage.

Seeming thoughtful, Clay then raises his platform to the surface level, inside a building.  He comments that you need to have good dancers in order to have a good show (raising all sorts of questions) and then heads South, leaving you alone until you go to follow him.  As it turns out, you're back at the entrance to the building.  Stepping outside, you'll find Hugh and Clay waiting for you together- your friend notes that you got a badge and enthuses that he knew you could.  He credits his own win to his pokemon partners, mentioning that he believes there's more of a connection between a person and their pokemon than just the poke balls will account for.