Lance gave me a lot of trouble after I beat all the Gym Leaders in HGSS.
I ran a full Water-type team in my last playthrough. Even with Feraligatr, Lanturn and Gyarados on my side, his Garchomp, Salamence and Gyarados were the most bothersome to deal with because of random crits, high speed and setting up, coupled with an AI that doesn't want the opponent to hurt itself in confusion after a very strong Outrage.
Red was also very hard to deal with, since his Venusaur was almost impenetrable, even with permanent Hail in battle.