Marshal in gen 5 was the hardest for me. His pokemon seem to be able to live through any flying or psychic move no problem, and then hit my guys with a supereffective rockslide or payback XD. I think he covered his weaknesses very well.
Gen 2 is the only one who gave me any trouble because the level balance is so bad. The Pokémon you meet on the way to the E4 don't give you enough EXP to face them. Once you get to a couple of levels below them they become as easy as any E4 though.
Gen 1: Never got to them Gen 2: Probably The dark type trainer... I don't know... Gen 3: Never got to them Gen 4: Lucian. F*** you bronzong. Gen 5: As much as I hate to admit, Caitlin. I never had any fire types for her Bronzong... Overall: Lucian without question.
Mentions of Zangoose since 6/27/2013 as of this post: 41 Official Shadow Zangoose of the X board and Salamence of PGD!