R/B/Y: I always use a Bellsprout or Oddish for Cut (and maybe Flash? I forget if they can learn it). Surf and Strength are usually on my main team. Same with Fly, because I'm lazy.
G/S/C: Bellsprout and Oddish for Cut and Flash. Surf, Strength, and Fly are on my main team. I think I usually get a Krabby for Rock Smash, and I use Gyarados for Waterfall and Whirlpool.
R/S/E: Linoone/Zigzagoon is pretty awesome. It can use a lot of HMs, and it has Pickup, which is pretty handy. I think I catch a Wailmer for Dive and Whirlpool and Waterfall purposes... was there Whirlpool in these games? I forget. Whatever.
D/P/Pt: One word. Bibarel.