For me, I use Furret, Linoone, or Bibarel, depending on the game. (In the first generation, I didn't bother with HM slaves.)
I think it's easy to use one of those three because they are available early in the game. (First route!)
They all learn Cut, Rock Smash, Surf, and Strength, which are handy to have on one Pokemon... For Bibarel, I sometimes substitute one of those moves for Waterfall or Rock Climb, depending on my party's capabilities...