Gen I: I've only just started playing through Red and only got 3 badges, but the hardest so far was probably Misty
Gen II: Whitney of course.
Gen III: Tate & Liza. Never go up against them with just a Blaziken and a Linoone!
Gen IV: I don't think any of them gave me that much trouble
Gen V: Lenora. Why are the Normal type Gyms always really hard??