Generation 3 was a bit of a tipping point in the metagame - it was between Gen 2 and 4, the former being very defensively-based, and the latter being the start of the "power creep". The Physical/Special split had yet to happen, and that split punished some Pokémon, and absolutely bolstered others.
While it's true that Gyarados was weaker as a result of a lower Special Attack, it still packed Intimidate and Dragon dance, which was pretty much a guaranteed spot in OU. Keep in mind that no Pokémon during this time was absolutely beyond powerful - having a base stat over 120 was considered a hugerarity, so by comparison, Gyarados was still incredibly powerful.
Salamence wrecked everything back in the day, as well. Packing Gyarados' same Intimidate + Dragon Dance combo on top of great Special Attack for Dragon Claw, Fire Blast, and Hydro Pump made for devastating sets. I believe Salamence was one of few OU standards eventually banned to Ubers for a time in gen 3, but was eventually sent back once Jirachi was released.
For people coming into the scene after Gen 3, there were a lot of fundamental differences in the nature of the game that should be noted:
Stealth Rock didn't exist. Instead, Spikes was the main hazard to lay down. Claydol, Smeargle, and Forretress were the main Spikers since they could Spin and lay Spikes down at the same time - another rare gift that is now pretty much mediocre to Spinning and Stealth Rock.
Unless you played Ubers, there was no instant weather. Welcome back to the pioneering days in Generation 6! Where you need to pack Damp Rocks and related items to make your weather team function.
Priority moves and boosting moves were few and far between simply because they didn't exist much. The only regular priority attacks were Quick Attack and Mach Punch, really. No Aqua Jet, no Sucker Punch, and no Bullet Punch. Boosting moves were also a bit rarer and easier to predict, mainly because of there being no Swords Dance TM and fewer Pokémon. It was usually fairly easy to tell which Pokémon were going to boost and which were just going to go for the sweep.
The huge kicker that messes with people when trying to go back and play Gen 3 is that there are way fewer items. No Choice Specs, no Life Orb, no Expert Belt, no Focus Sash, and the worst offender to modern metagamers, no Choice Scarf!
Gen 3 in general left many sets to be pretty open-ended and creative, since you couldn't depend on the strength of a hold item and/or ability to carry your weight (Looking at you, Talonflame). The existence of the Choice Band, however, made a lot of the metagame leaning toward physical-based attacks, on top of the expansion of Ghost, Rock, and Steel-types offsetting that trend. Double powder Butterfree was usable in OU, and SubPunch Alakazam was totally viable, I'm not kidding.
Hoenn was very much a beast of its own - it wasn't about Curse boosts and ResTalk sets like the Johto games were, and it wasn't flat-out broken like Red and Blue. It the first and last of its kind: a classic-era metagame that looks a little bit like the modern era's, but is still very different.
Hope I helped to some degree - sorry for the long answer!
