I'm going to recommend either Tentacruel or Gyarados, depending on the needs of your team.
Tentacruel is an absolutely wonderful HM slave, it's specially bulky, and it learns some decent moves. Tentacool can be found almost anywhere there's water, and water's everywhere in Hoenn. It evolves at the reasonable level 30.
Gyarados is better if you'd prefer a physical powerhouse. While Magikarp is worthless, it can be fished up almost anywhere, and evolves at just level 20. Gyarados learns a ton of great moves, and it's a nice addition to any team.
Tentacruel @ anything
Ability: Clear Body / Liquid Ooze
- Cut / Sludge Wave / Sludge Bomb
Gyarados @ anything
- Waterfall / Aqua Tail
- Ice Fang / Strength
Hope I helped!