Pallette Town with the Super Rod.
(Yes, you need the Super Rod in Fire Red.)
Chat with our AI personalities
You wil have to trade with FireRed or XD.
Use a good rod in seafoam islands.
Poliwhirl → Poliwrath, Shellder → Cloyster, Staryu → Starmie and Eevee → Vaporeon
lombrea, evee, poliwhirl, shellder, and staryu. some of these can only be found in firered and leafgreen so you will need to trade. that's all I can think of.
You cant find it in Firered only leafgreen.