I'm surprised he hasn't been mentioned much before, but Giovanni in RBY and FRLG. Especially the latter, why did they replace his Rhydon with another Rhyhorn?
It's so disappointing, most of his team is really slow (apart from Dugtrio who's weak both offensively and defensively), and you just OHKO everything with Surf. Lt. Surge and Blaine were always ridiculously easy too. You don't even have to try. At least the Persian in Yellow was a bit more interesting.
RBY gym leaders did tend to have much stronger teams, but often their Pokemon knew just their normal level-up moves (maybe + the TM the gym leader gives you), and the AI is stupid, almost seeming like it just uses random moves. In the later generations, at least the AI and movesets are better (they generally use the strongest move against you, and sometimes even switch Pokemon), but the levels are really low.
There are sometimes in-game battles I find difficult, but usually it's just too easy. A mixture of the high levels from Pokemon Yellow (battling L.50 Pokemon at gym 5 is more like it), and the more intelligent AI with better movesets from the later games would be good.
GSC was the easiest of all, especially the Kanto section. I'm glad they made it more difficult for HGSS.