The Gym that I found easiest out of any of the games that I've played was in Oreburgh against Roark. Maybe it's because I over-trained my Prinplup going into the battle (one of the few times I've evolved my starter prior to the first Gym), but it seemed like I absolutely steamrolled his Pokemon, whereas in other first Gyms the Leaders put up a bit of a fight. Bugsy would probably be second on my list, just because I generally pick Typhlosion, which makes the battle awfully easy.
1st gen (Yellow): Misty, Pikachu use Thunderbolt! xD
2nd gen (Gold): I can't remember, maybe Bugsy?
3rd gen (Ruby & Emerald): Roxanne, Mudkip (well Marshtomp, I tend to overgrind xD) use Mud-slap! xD Use Water gun! xD xD
4th gen (Diamond and Pearl): Roark, Rock type normally tends to be easiest for me (Twiggy, Turtwig xD)
4th gen (Heartgold): Believe it or not, Whitney. Clefairy? Geodude, Rock Smash and it worked. Miltank? Geodude, Selfdestruct. Like 3 or 4 moves xD
5th gen (Black): Maybe Clay, because like Rock, Ground tends to be fairly easy for me.
Roxie (if you have a Magnemite), Burgh, Skyla, Brycen, Marlon, Falkner, Bugsy, Jazz, Pyrce, Candice, Byron, Koga/Janine, Blaine, Giovanni, Lt. Surge, Flannery, Brawley, Tate & Liza, Wallace, and every single Rock gym leader.