My main HM slave in Sapphire was always Tropius. It would generally have Cut, Flash, Fly and Rock Smash. Funny enough, I remember my other HM slave from my original run on Sapphire was Kyogre. I was already at the point where I didn't want to use Legendaries on my team, but I justified it as being okay to use since it could learn the other four HMs. Looking back, I feel awful for making a legendary one of my HM slaves.