In FireRed/LeafGreen, only Cut, Strength, and Surf are necessary until the postgame, while Fly can be used for convenience. Flash is only necessary for Rock Tunnel later in the game, so just slap it onto a random Pokémon for the one area, while you won't be getting Cut until the S.S. Anne. As a result, a Pokémon dedicated to HMs isn't necessary until after the second badge. Catch a Spearow and trade it for Farfetch'd in Vermillion City, which can learn both Cut and Fly. Later on, you'll obtain a Krabby for Strength and Surf from fishing with the Good Rod, assuming you don't already have a Water-type to teach it to.
In Ruby/Sapphire/Emerald, get yourself a Nincada for Cut and Flash, and Marill for every other HM besides Fly for later in the game. Tropius should replace Nincada, as it and Marill can learn all HMs in the game. You may also replace Nincada with Sableye early on, as then only one HM mule is necessary until Strength.
I excluded starters from these picks, as it's likely they'll be used as playthrough Pokémon. However, Bulbasaur and Treecko are the best respectively.
