Mm! In Crystal, I caught a Flaafy on my way to the Lake of Rage for whatever reason.
My brother's friend traded me a Crobat, but I reset that game.
In Sapphire, I caught a Zigzagoon, and an Aron a few hours after that. Then some time later, I got a Tentacool surfing around somewhere. In LG, on my way back from the Aide's house that gives you Cut, I caught a Diglett. Then later, EV training one of my Pokémon, I got another Tentacool in the abandoned ship. Later, I got a Poochyena.
All legit, too. ^_^