To verify the Single FW rule thing...
Its only for ranked games. If we ranked, say, Onix alone this time, he would not conflict with the other options, cause RBY is "Ranked", and he's a lone FW from a ranked game. However, if we ranked Empoleon, he'd count since he's a new game.
The FW from Already Ranked Game mostly applies to the first stage only. They still count as a Nom Slot, HOWEVER, they do not count towards the "2 highest move on"; if an FW from a Ranked Game is >= to the #2 game on the list, it moves on along with them. Again, this is for RANKED games only and its SINGLE FWs; a group of FWs would probably count as a whole game slot.
That said...
Nitpicking, but Elfboy, did you mean HYdro Pump when you said Surf? Granted, for DL purposes, they're very similar, and only really matters when Starmie faces other healers but still (Granted, Confuse Ray can futz up Healers, and it can try stall tactics...its almost like Starmie has *gasp* OPTIONS DL legally!)
Anyway, Gen 1 Gyarados was utterly generic Water Type; good SpA, but it didn't stand out at it, IIRC, and just had unique typing; Starmie was generally considered one of the best of the original 150 PERIOD. Being the best Water type is nothing to scoff at considering how many quality Water types tehre are *AND* its a pretty big typage. While Starmie no longer has that "Best Water Type EVAR!" thing, its still a contender and worthwhile put on teams, both in game and competitive, so yeah, I won't go into detail about him in later gens.
Gen 2, Gyarados is so horribly useless its not even funny, Gen 3, he got a little better...cause of TMs and Intimidate. He's still not exactly a good option, just doesn't embarrass himself the way he did in Gen 2; its really only in Gen 4 that he lives up to its Plot/Anime Hype, when all those fun physical options come into play.
Oh, with regards to Anime, Gyarados can't even really bank on that; Misty's best Pokemon were Starmie and Staryu (Starmie left after a point, but I believe she always had Staryu after that still, and it was generally her best due to lack of Starmie?), Gyarados just popped up arbitrarily when they wanted MENACING WATER TYPE in the show. Basically, while the anime is a bad thing to go off of, I'm just indicating that even using the anime as a trump card, perse, it doesn't help Gyarados' case, cause Starmie counters appropriately.