Brock in Pokemon Yellow is probably the hardest for me. The only options to beat it at that point are Mankey/Low Kick, Nidoran/Double Kick and Butterfree/Confusion. And those are difficult to get, as you have to train them to high levels (my team is usually L6/L7 by the time I get to Brock). Also Sabrina in Pokemon Yellow again (mainly because Psychic types are so broken in that game). I honestly never found Misty difficult, in any game. I don't get why people found her so difficult lol. I mean, Bubblebeam is strong, but she uses X Defend like every turn, you always just Leech Seed it. Others I found difficult were Watson in RSE (mainly because of Magneton and its resistances), and Whitney in Gold (because of Miltank obviously). I don't know if they count, but Pokemon Stadium 2 had the hardest NPCs of any game by far.