I'm having serious problems with this issue as well, however I'm at the Elite Four right now. Since many good Water Types are obtained after Surf, I would get something like a Marill or Tentacool now as an HM slave and surf over to get the Good Rod. This can get you a multitude of Pokemon such as Carvanha, Wailmer, Barboach, and Corphish. However, the best success with this I had in a previous playthrough is to wait all the way until Shoal Cave and get a Spheal. Walrein is a beast. You can pick whichever suits your needs, but I will offer one piece of advice. Never. EVER. Use a Seaking. I'm sure I never will again. Thus is why I'm looking for a new Water type when I'm on the E4...