All of my stories relating to the Gym leaders are rather positive so far. I took down Rorak with my Turtwig alone, then ripped through Gardenia in a similar fashion with my Staravia. Maylene amused me a bit because I fought her rather cheaply. I took out her first two Pokemon with my Staravia, then switched in Grotle and used Curse a few four or five times. During this process I did have to heal twice, and she DID use a Hyper Potion once, but in the end my Grotle managed to take Lucario down without much fuss.
The only other Gym Leader I've taken on so far is Crasher Wake, and he only did me a favour by using Swagger on my Luxray (who I promptly used a Full Heal on then took the Gyarados out easily). I then switched my Grotle in to finish off the rest of his Pokemon and was rewarded with my long awaited Torterra evolution ^_^
So, yeah... Me thinks I was a bit over leveled for Wake. Either way, not much of a challenge.