This was a fun spreadsheet to make. I have come to the conclusion that Gyarados is the most optimal HM slave you listed. But can also easily be swapped for a Sharpedo later.
For starters, Gyarados and Sharpedo have the same HM learned with 5, while Tentacruel only has 4, not having access to Rock Smash and Strength but gaining Cut in their place. The problem is you never need Cut to advance the story, while you do need Strength and Rock Smash.
Next, you can catch a Magikarp much sooner then a Carvanha, being available immediately after getting the Old Rod in Dewford Town, (alongside Tentacool, if that still interests you) while Carvanha can at its earliest be found on Route 118 at a measly 5% encounter rate with the Good Rod. With how easy it is to obtain the Exp Share you can Viable have a ready Gyarados before you cam even encounter a Carvanha.
Gyardos also provides the most utility in battle with its great 540 base stats, including a base 125 atk stat with good bulk and the ever powerful Intimidate Ability. Sharpedo however comes with an Abysmal 460 base stat, supplemented by his only slightly lower 120 Base atk and dismal defenses.
The only real area Sharpedo excels over Gyarados at, is its special Surfing animation have a much faster speed then the ordinary one that Gyarados uses.
Hope I Helped.
