Each one has good and bad points. Gastrodon has 1 weakness, Tentacruel is a special wall, Milotic is very strong in terms of special, where Gyarados is a physical sweeper, and Azumarill can be a defensive wall. I will cover them all.
Gyarados
STATS
Weaknesses:
> Electric (4), Rock (2)
Gyarados has a wonderful moveset, can learn Dragon and Fire moves. It also has a immunity to Ground
Recommended Moves:
Waterfall
Avalanche
Earthquake
Dragon Dance
Location: Route 203, 204, 205, 208, 209, 210, 212, 213, 214, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, Canalave City, Celestic Town, Eterna City, Fuego Ironworks, Great Marsh, Iron Island, Lake Acuity, Lake Valor, Lake Verity, Mt. Coronet, Oreburgh Gate, Pastoria City, Pokemon League, Ravaged Path, Resort Area, Sendoff Spring, Sunyshore City, Twinleaf Town, Valley Windworks, Victory Road
Gastrodon
STATS
Weaknesses:
> Grass (4)
Gastrodon is a tank, and has a good special attack. It has a immunity to Electric, but there aren't very many electric types in Diamond and Pearl
Recommended Moveset
Surf
Dig
Ice Beam
Sandstorm
Location: Route 218, 221, 222, 224, 230, Fuego Ironworks
Tentacruel
STATS
Weaknesses
>Psychic (2) Ground (2) Electric (2)
Tentacruel may have 3 weaknesses, but two of them are mainly special, and Tentacruel is a great tank in this game. Plus a good speed to get rid of Ground types.
Recommended Moveset
Surf
Giga Drain
Sludge Bomb
Blizzard
Location: Route 205, 213, 218, 219, 220, 221, 222, 223, 224, 226, 230, Canalave City, Fuego Ironworks, Iron Island, Pastoria City, Pokemon League, Sunyshore City, Valley Windworks
Azumarill
Weaknesses
>Electric (2) Grass (2)
Luckily, Azumarill isn't a fairy type back then, but at least you can easily run a mixed set.
Recommended Moves
Surf
Waterfall
Brick Break
Toxic
Location: Great Marsh, Trophy Garden (Marill)
Milotic
STATS
Weaknesses:
>Electric (2) Grass (2)
Milotic is very good when in competitive scenes. It can take hits and dish them out harder. Though evolving it is rather hard
Recommended Moves
Surf
Dragon Pulse
Attract
Toxic
Location: Mt. Coronet (Feebas)
I would say Gyarados, because it is easy to find, has a good moveset, doesn't have to worry about electric types being around. and can easily destroy rock types. It also has a 540 stat total. It can also be a HM slave. But it all depends what you are looking for in the team.