Gyarados should be high imo: it has decent HM slave utility in the very least. You need to clear Pokemon Tower to get him (Super Rod is on Route 12...Snorlax >_>") but chances are you can get him at a good level (something like LV23 or so). With Thrash, he makes a good choice for most things you fight at that point(rockets). You honestly shouldn't bother with Magikarp since it's not only a pain, you also can't get Thrash onto Gyara. When you get Gyarados you should also be able to go down to Fuchsia and nab Surf, giving him a reliable STAB. Intimidate makes him bulky on both sides of the spectrum and the attack drop can also help another teammate get in safely. His typing is great: you really only need to watch out for Electric and Rock, which aren't very common in the game.
@Lucchini: it's a Super Rod, but it doesn't matter since both come at the same time...