I never had much problems with Gary/Blue/Green/whatever you call him like, he's easy to beat even with an underleveled team, only his Alakazam can cause trouble. But i've never played FR/LG a lot, maybe it's different there.
Lance is harder, but so underleveled and extremely weak to Ice and Electric, two common attacking types, so he isn't that much of a problem.
Steven... Again, a specialized Champion, extremely weak to Ground and Fightning, which are - again - very common.
Wallace has that damn annoying Ludicolo, but again, he's using just one type, and Electric is a common attacking type.
Cynthia is definetely the hardest in my opinion, unlike Gary, all of her Pokemon (except for maybe Gastrodon in D/P and Roserade) often cause serious trouble, and unlike the others, she isn't horribly weak two one or two types.