I remember Red and Crystal were fairly easy. Fire Red was moderately challenging (though second time round, the E4 are just deadly if you're unprepared). When I played Sapphire the first time round, the E4 were just average at best, but I remember on my first Ruby playthrough, I had some serious problems with Drake and I lost the League a few times. (Came back with a Walrein
).
Diamond was, once again, a decent challenge; same with Platinum. In fact, my second time in Diamond was tougher than my first, since I wasn't as high leveled and my Pokemon weren't really the strongest - so it took quite a while getting past Cynthia. Actually, if you don't train properly or are ignorant about type matchups, etc. all the game are fairly hard, comparatively very challenging in fact - I noticed this watching one of my friends play, who's somewhat new to the games.
Now, HGSS, imo, is the toughest game till date. That still doesn't mean it's a very tough game, but by Pokemon standards, the thing can be called hard. You'll definitely run into problems with a few of the Gym leaders, if you haven't been grinding endlessly, because really - there's just no good place to train before you beat Clair and catch Ho-oh. So, the Gym Leaders levels will be quite high and battles won't be pushovers (Morty, Clair and to an extent, Chuck are probably the most dangerous.) The E4 isn't all that strong, but Lance is definitely dangerous if you're unprepared for his Dragons. Kanto gyms are OK I guess, but the true test is against the second round E4.
No, wait. Scratch that. It's Red. Yeah, the strongest trainer in Pokemon makes for the toughest boss battle, especially if you play without items (or limit them) and put the battle Mode on "set".