Easiest: Adler and Blue. Adler had bad coverage, using three Pokemon that were the Bug-type, and his moves weren't super powerful. My Emboar alone decimated him. It was almost pure child's play. Blue was also easy. Just had to know when to swap out for the right battle situation, but, again, that was easy enough to do.
Hardest: Wallace and Cynthia. Wallace in Emerald was a pain first time around. The only Pokemon I had that could effectively fight him was a Manectric, so in order to mitigate that, I traded over a Treeko from another version and raised it up to a Secptile. Barely got through that one, though.
However, Cynthia was, by far, the toughest Champion of them all. She had almost perfect, if not perfect balance, the ability to mitigate her weaknesses with almost ridiculous ease, perfect IVs, near perfect stats and moves, and her levels were almost astronomical at that time. Considering the level gap between the E4 and Gym #8, I spent a goodly amount of time training in Victory Road just to try to match those levels, let alone trump them. She was definitely the champion of champions, and still is. Her Platinum team was probably her best team for her gen, though her Gen V team is also a royal pain. I struggled against her, especially her Spiritomb, Milotic and, of course, Garchomp. When I first beat her, I was like, "Wow... I actually won. I didn't know if I could do it, but I actually beat her." So, Cynthia deserves the crown for strongest, and toughest, Champion in the Pokemon Universe.