The first time around the only leaders that really gave me trouble were Tate and Liza [I had no idea Tate was a boy til I read it on Wikipedia [Random fact for you there :P]]
But the second time around I've sailed through them all. I just took Gym 7 down with Grumpig [Confusion to protect Gyarados] and Gyarados [Surf and Dragon Rage just to finish them off]