I'd have to say Gyarados for a few reasons. The first being, you can get Magikarp really early. Just go to the gate west of Jubilife City and talk to the fisherman. From there you can go west outside of the gate to fish for Magikarps. The second reason is, because of a certain blonde in the game. Gyarados being a flying type and having the ability intimidate will help you big time against the blonde. The third reason is dragon dance. If you know your opponent cannot kill you in one or two shots, use that to dance up and use potions to heal Gyarados then just one shot everyone. It's only downside is it is a pain to level up