I actually chose Piplup to start (don't ask me why, water ones have seemed to be easy to get) and steamrolled the first gym (rock types hehe). My party's pretty diverse (Piplup, Starly, Bidoof, Machop, Shinx, and Kricketot) and I haven't run into anything terribly difficult so far. That Kricketot had better evolve into something kickass, because I hate having Bide as his only attack and I don't want to waste a TM if I don't have to.