Let's see:

Tentacruel
Pros:
Impressive SpD, which means it can tank Electric and Grass well, since said types are both Special-only prior to Generation 4
Pretty quick, allowing it to outspeed
A really great HM Holder
Found very early
Cons:
Not that great in battles
Overall stats outside of SpD and Speed is not that great

Sharpedo
Pros:
Well rounded offensive and speed stats, with 120/95/95 respectively
Pretty fast and quite the tough cookie if trained enough
Decently utilizes STABs with a decent 95 base SpA
Cons:
Slower than Tentacruel by a mile
Found a little later as a Carvanha
Fishing isn't the best thing to search Mons' for in Gen 3
While it decently utilizes its' STABs, its still not optimal
In conclusion, I suggest Tentacruel the best. While not the best in brawls, it can be a good HM utilizer outside of battles, where HMs are a key to the main game.

Tentacruel @ Any
Recommended Nature(s): Modest (+SpA -Atk)
Ability: Clear Body/Liquid Ooze
- Surf
- Waterfall
- Any HM/Move
- Any HM/Move
.
.
However, there are certainly another option that you can use:

Walrein @ Any
Recommended Nature(s): Timid (+Spe -Atk) / Modest (+SpA -Atk)
Ability: Thick Fat
- Ice Beam/Blizzard
- Surf/Hail
- Any HM/Move
- Any HM/Move
Walrein is found a little later than the two previous options, but it is quite worth it. It has a decent defensive and HP spread, and can utilize its STABs well. Found as a Spheal in Shoal Cave.
Hope I helped!