Azurill - High Tier
Availability: You can get it before the 1st gym. Only warning is that you must catch one with Huge Power, or else it's dead weight.
Stats: Early on, it has mediocre 50/40/40 defenses and has a somewhat hard time of taking hits. However, the essentially 100 base attack is absolutely insane early, and once it evolves into Azumarill, is packing base 150, with surprisingly good 100/80/80 defenses. Its speed hurts a little though, since you cannot get one with Aqua Jet before you beat the game.
Typing: Azurill's Normal typing is a great offensive typing early on, with the ability to abuse Frustration and Return until it evolves, and mediocre defensively because while its one weakness (Fighting) is very uncommon early on, no resists hurts. Azumarill's Water typing is amazing offensively, with the ability to spam Aqua Tail/Waterfall, but not great defensively, due to how common Grass and Electric moves are in game. The Fire and Ice resists help a lot, though.
Movepool: Almost immediately after you catch Azurill, you get Frustration, which you can abuse until its happiness gets high enough, in which you just swap it out for Return, which you get not long after. It also starts with Charm, which is a surprisingly good move against Cheren, but loses value after that battle. Helping Hand can be a good situational move in doubles as well. Azumarill's level up movepool is amazing. It gets Aqua Tail very early, and not long after, gets Double-Edge. It later gets Superpower at level 42, which completes the amazing Water/Normal/Fighting attack type trifecta that hits everything in-game for at least neutral damage. It is not reliant on TMs, as the only ones you might end up giving it are Waterfall and Return/Frustration, both automatically obtained in-game. The only move you might have to sidetrack for is Ice Punch, but there is an NPC around this time who gives you 10 Red Shards, which is just enough to tutor Ice Punch onto it.
Major Battles: Azurill with Charm can easily defeat Cheren by nullifying his Work Ups. It does OK vs Roxie, but has a hard time with Koffing. By the time you are at Burgh, you will probably have Azumarill, and it can OHKO Dwebble, but will have a hard time with Swadloon and Leavanny. It does surprisingly well vs Elesa, due to having the bulk to survive a Volt Switch, then proceeding to do high damage or OHKO whatever she switches in (watch out for Static, though!). It easily rolls over Clay and does OK against Skyla. If you tutored Ice Punch, it rolls over Drayden. Marlon is a little tough, though.
Against the E4, Azumarill does very well. It defeats 3/4ths of Shauntal's team (Cofag is a 100% counter against it, because of its high defense + Mummy), Grimsley either gets Superpowered (Liepard, Bisharp, Scrafty if you're feeling lucky) or Waterfalled (Krookodile), Caitlin is Waterfalled or Ice Punched (switch out vs Gothielle, though), and Marshal is Waterfalled. Iris is pretty much destroyed. Everything she has is weak to Waterfall, Superpower, or Ice Punch. Against Plasma, Azumarill does fairly well, hitting most things with Waterfall or Superpower, and the occasional Ice Punch.
Additional Comments: Use Huge Power or else it sucks. It gains EXP very fast as well, so expect lots of level ups. Lastly, you can get a Mystic Water very early, right after the second gym. The 20% boost to Aqua Tail/Waterfall can save you at times.