The best ways are to fish or surf. You can either use the Good Rod on one of the routes, or wait until you get HM03. I suggest surfing in that little pond in Celadon City; I think they can be found there, and it's not a lot of space to cover.
I don't think Slowpoke can be fished up unless you're using the Super Rod, which is available as soon as you are able to wake the sleeping Snorlax west of Vermilion. Once you have that, it's available pretty much any place there's water, though the chances tend to be slim (like, <5%). The percentages get higher on later routes (as well as Surfing and walking in places like the Seafoam Islands), but that involves waiting longer to get one.