...and if you choose to go after Horsea, you can find them by fishing with the Super Rod in the fast-moving currents within Routes 132-4. Horsea aren't much more common than Bagon, though. I prefer going after Horsea because my item stealer is a Linoone, and it can cope with Wailmer and Sharpedo better than it can cope with Solrock.