From Information I've read from Serebii.net on their large Pokedex, Horsea are common and are found in Whirl Islands and Seafoam Islands. There's a much higher catch rate if you Surf for the Horsea, but you can also use a good or super rod, which is a little harder. Hope that helped you!
