The best HM slave is definitely Bibarel, capable of learning Cut, Surf, Strength, Rock Smash, Waterfall, and Rock Climb. Bidoof and Bibarel are common and obtainable early. Tropius is available later, in the Great Marsh, and learns Cut, Fly, Strength, Defog, and Rock Smash, perfectly complementing your beaver. Alternatively, Starly can learn both HMs that Bibarel can't and is also available before the first Gym, but it doesn't do anything Tropius can't.
A good "team" of HM slaves is one Bibarel and one Tropius, which together learn all eight HM moves and allow you to manage experience among a smaller battling party of four members.
A slightly worse team of HM slaves consists of two Bibarel and one Starly, which allows you to teach every available HM with Pokemon available earlier. This has little practical bearing, however, as many HMs aren't obtainable until after you catch Tropius anyway.
