*Puts on nerd glasses*
Gyrados is double weak against electric types and can do nothing to defend against them.
Squirtle can be taught Dig, to both defend and attack against electrics, and blizzard, giving him the upper hand against grass types. A Blastoise with Dig, Blizzard, Surf and Hydro Pump will seldom let you down.
Actually...
With base 95 HP, base 79 defense, and base 100 special defense, Gyarados is actually surprisingly bulky. While he's weaker on the physical defense side, he comes with the ability Intimidate, which cuts the opposing pokemon's attack in half right off the bat. This means he can tank physical hits despite having a lower base defense than special defense. Yes, he's 4x weak against electric attacks, but if he switches in on a non-electric opponent, he actually has a good chance of surviving whatever attack they throw at him. Yes, sometimes even electric attacks.
Oh, not to mention that Gyarados's flying/water typing makes it weak to two types (electric and rock), but resists five (water, fighting, bug, steel and fire), while also making him immune to ground type attacks. This means that unless your opponent has an electric type on the field, you can probably switch Gyarados in fairly easily, and count on it surviving.
Then, after switching in, depending on the moveset you use, you can utterly destroy your opponent. The most effective set is probably the Dragon Dance set, which involves using Dragon Dance to boost Gyarados's attack and speed. After one boost, you'll outspeed most of your opponents, plus you'll have 50% higher attack. Coupled with Gyarados's base 125 attack stat, and you can often sweep your opponent's team. If you manage to accumulate more than one boost, your opponent might as well surrender.
An effective set would look something like Dragon Dance/Waterfall/Earthquake/Stone Edge. Dragon Dance for the boosts, as mentioned already. Waterfall for the physical STAB (same type attack bonus, which increases damage by 50%), Earthquake for the inevitable electric type that's going to switch in, and Stone Edge for flying types such as a lot of the common dragons, and even opposing Gyarados.
Of course, more advanced players can use a strategy like Motor Drive bait. Motor Drive is an ability found on Electivire, which means it's immune to electric attacks, and actually gets a speed boost when it's hit by an electric attack. So by putting Gyarados on the field, you're basically screaming "hit me with electric!" And then you switch Gyarados out and have Electivire take the electric attack (and thus get a speed boost). Electivire then sweeps the opposing team with its base 123 attack stat, and huge movepool.
Oh, and for starter, I gotta go with Mudkip. Its final evolution Swampert is an utter beast. It has only one weakness (grass) and has two great STAB types to attack with. Not to mention it can support its team with Stealth Rock.