Gyarados
With good stats all around, having an amazing Attack stat, good bulk and decent Speed, plus good STAB moves and coverage, Gyarados is definitely a great Pokemon, and one of the best available to you in Platinum. It can be caught easily and very early, and has room in its moveset for multiple HMs while also functioning as a powerful member of the team.
Gyarados @ Splash Plate
Ability: Intimidate
Adamant Nature
- Waterfall
- Bounce
- Earthquake / Ice Fang
- Surf
The Splash Plate boosts Gyarados's Water type STAB moves, which are the moves you will be using most often. Intimidate is a great ability, as it minimizes the amount of damage Gyarados takes from physical attackers, meaning you will have to heal less often. An Adamant Nature is the best to boost your Attack while not lowering any other important stats. Since you will usually be outspeeding because this is ingame, a Speed boosting Nature is not needed. Waterfall is good STAB and a useful HM. Bounce is Gyarados's best Flying type STAB and hits Grass types hard. Earthquake is Gyarados's best coverage move, hitting Electric types super-effectively; however, you may have need to teach this to your Ground type Pokemon. If so, Ice Fang is another decent option. Surf is the last move, and while you won't be using it in battle much, it is an extremely useful HM.
Gyarados can be obtained very easily. In Jubilife City, go west towards Canalave City. While you are doing this, you will meet a fisher who will give you an Old Rod. Keep going west and you will hit a body of water. Fish here and you can catch a Magikarp. To train it up, equip Magikarp with the EXP Share, which can be obtained in Eterna City near the entrance of the Cycling Road. Level up Magikarp to level 20, and bam, you have a Gyarados.