As the very first Gym Leader, Brock has received the largest upgrade. Still, he’s pretty easy if you have reliable Water and Grass-types.
First up is Brock’s trusty Onix. It can use Rock Slide and Earthquake for STAB, Iron Tail to damage Fairies etc., and Stealth Rock to hurt Pokémon that you switch in. Water and Grass are ideal, since they deal quadruple damage, and you want to quickly KO it before it uses Stealth Rock.
Next, he may send out Omastar, one of his three fossil Pokémon. This one can use Hydro Pump for STAB, Blizzard to hurt Grass-types, Seismic Toss to deal 56 damage, and Reflect to dampen your physical attacks. If you have one, now’s the time to sick your Grass-types on it. Electric-types are also good here.
Golem is Brock’s “main” Pokémon, although it’s not much stronger than his rest. This one can use Rock Slide and Earthquake for STAB, Fire Punch to hurt Grass-types, and Thunder Punch to hurt Water-types. Still, Grass and Water will rule surpreme here.
Aerodactyl is another fossil Pokémon–and quite possibly the most dangerous one. It can use Rock Slide for STAB and to potentially cause flinch, Earthquake to pummel Electric-types, plus Iron Tail and Crunch. Water-types are the safest choice, so long as they’re not weak to Rock. Looking at you Gyarados.
Finally, Kabutops completes the trinity of fossils. This one can use Rock Slide for STAB, Aqua Jet to try and go first, Brick Break to shatter barriers, and X-Scissor. Like Omastar, Grass-types are ideal here because of their outrageous damage. But non-Poison ones should be wary of X-Scissor.