I too thought the Red Gyarados was something of an easter egg. I caught it, used it, and thought "Hey, Red Gyarados is cool. Wish they'd do stuff like that with more Pokémon".
Later in my Crystal game, I encountered a pink Magmar. "Was that a pink Magmar? Oh, now I get it, it's a Ditto having transformed into a Magmar! Cool, I didn't know they could do it like that."
Then I proceeded to Surf it to oblivion for the sake of training my Golduck. It took years before I understood what I had done.
It was on FireRed I found the first Shiny I could recognise. A Pidgeotto suddenly leaped at me while I was training on Three Island (the Bond Bridge area). I saw the stars, the alternate coloration, and happily caught it without any problems. It became my main flyer and "team support" Pokémon, whenever I was training weaklings, I brought Pidgeot (whose level eventually reached into the high nineties) to take over the fight if things got messy.
Some later time on FireRed, at a place I can't remember, I found my second Shiny: Pidgey. Can't remember what I did with it, it didn't seem as special when I already had got a shiny Pidgeot, trained for years as a member of my main party.
I've also found a shiny Starly and Kricketune on Pearl, and a Lotad on Emerald. Apart from the last one, the shinies I find tend to be quite boring ones.