When I faced the gym leaders in Diamond/Pearl for the first time, here's how it went:
Roark: He was surprisingly difficult to beat. I had all my Pokemon at level 10, and picked Turtwig as a starter, but his Cranidos was difficult to beat--it was both fast and had high Attack. I ended up narrowly defeating him with my Starly... In future games though, I raised my Pokemon to level 15 and thus was able to beat him much more easily.
Gardenia: Not that difficult with level 20 Pokemon. When I faced her in Pearl I had Drifloon and Combee on my team, and my Combee especially was able to resist the Grass attacks, and because she was light, she took about 1 damage from Grass Knot. I wore her Pokemon down with Gust.
Maylene: Her Lucario was a bit tricky, especially since none of my Pokemon had a Fighting or Fire or Ground-type attack, but fortunately I had a Misdreavus on my team and she was immune to fighting attacks (although all her attacks weren't very effective against Lucario).
Crasher Wake: That Floatzel OHKO'd my Roselia with Ice Fang, and all my Pokemon were slower than him. Even my Luxio was only able to get in one Spark before being KO'd. I think it was my Prinplup who finished him off.
Fantina: The funny part about this battle was that both of us had Misdreavus and Drifblim in our team, and my Misdreavus beat hers. My Luxray was able to handle the rest of her Pokemon pretty easily, knowing Bite, but Drifblim took a little while because it knew Stockpile.
Byron: This was an easy battle, save for his Bastiodon having high defenses. My Purugly was able to KO him in two Digs, and my Empoleon OHKO'd his Steelix with Surf.
Candice: The easiest of the gym leaders in my opinion. My Vespiquen 2HKO'd her Abomasnow with Attack Order and all Abomasnow did inbetween was use Wood Hammer, which only did a sliver of damage. The stupid plant didn't have the sense to use an ice attack! The Medicham threw me off, but my Mismagius OHKO'd it with Shadow Ball.
Volkner: He was pretty easy to beat. The funny part was that my level 47 Luxray beat his level 49 Luxray, without any items. His Luxray kept using Charge Beam or Thunder Fang, whereas mine used Crunch.
Aaron: The hardest of his Pokemon was Heracross, who I had to use Perish Song on in the end. Fortunately my Luxray was able to take care of his Vespiquen, and the other Pokemon weren't too hard.
Bertha: She was the easiest of the Elite Four. My Roserade OHKO'd her first two Pokemon (Quagsire and Whiscash) with Petal Dance, and the rest of the Pokemon surrendered to Roserade and Empoleon pretty easily.
Flint: The hardest of the Elite Four (Cynthia doesn't count). Sunny Day foiled my plan to beat him with my Empoleon's Surf, and Infernape KO'd my Purugly before she could use Dig or Dream Eater. I barely scraped by with my Mismagius there...
Lucian: He wasn't too hard to beat, actually. I had a Luxray with Crunch, a Vespiquen, and a Mismagius, and all three of them were able to handle the psychics.
Cynthia: This was a tough battle, especially since my team was just below level 55. The most unfortunate incident in that battle was when my Vespiquen battled her Lucario. It was a LONG battle, and my Vespiquen wore Lucario down with Attack Order and using Defend/Heal Order inbetween. When she finally KO'd Lucario, she had maxed-out Defense and Special Defense, so I thought she would do fine against Milotic. Wrong--Milotic's first Ice Beam got a critical hit. x_x