Note: I rarely if ever use Fly since I like to walk to places, so I often skip it entirely when picking Pokemon to use HMs.
Kanto: Paras learns Cut and Flash which are really the only HMs you need until you reach Fuschia City. At that point I switch over to Krabby, since Flash is only necessary for Rock Tunnel and I can use Cut/Surf/Strength to get through everything. It also learns Rock Smash in FRLG. For FRLG's postgame, I really only need to use anything else for Icefall Cave, since there's only one Waterfall that actually blocks off an obstacle.
Johto: If I didn't pick Cyndaquil or Chikorita, I use Crocanaw (hatched if I use Feraligatr on my team) to run Cut/Surf/Strength/Waterfall, and Golduck for Rock Smash/Whirlpool/Rock Climb. Otherwise I use Furret for Cut/Surf/Strength/Rock Smash and Golduck for Whirlpool/Waterfall/Rock Climb.
Hoenn: If I'm not using a starter, Treecko has everything I need up until I get Surf. After that point, Corphish has Cut/Surf/Rock Smash/Waterfall to get me to most places around the map, and a Tropius/Wailmer duo for anything that requires Flash, Dive, or Strength. (i.e. Victory Road or anything underwater.)
Sinnoh: Bibarel can learn all the necessary HMs, leaving only the unnecessary Fly and Defog. I don't usually care about the former, but if I didn't pick Turtwig or Chimchar, I use a Prinplup (hatched if I actually use Empoleon on my team), for the remaining two HMs and Defog, or just another Bibarel otherwise, and maybe a Starly for the one place where Defog is actually mandatory.
BW1: I'd go Patrat for Cut, then switch to Dwebble for Cut/Strength, then Cubchoo for Cut/Surf/Strength, and finally a Bibarel with Cut/Surf/Strength/Waterfall for the postgame.
B2W2: Corphish since it can learn all the non-Fly HMs you need until the Abyssal Ruins.
XY: I usually go with Froakie as an HM slave if I'm not using a starter in my team, otherwise I use Bunnelby up until I need Waterfall and Corphish afterwards.
TL;DR: Corphish is an HM MVP that's perfect for the job in any game where it's available.