I have to say that Gyms and Elite Four has good levels, but maybe they could increase them a little.
Falkner: He has too low leveled pokémon, Pidgeotto needs more levels, even that first trainer in gym has lvl9 Spearow. This gym could be harder, lets think about Brock in R/B/Y, you needed to get something super effective move, because your normal attacks are so bad against Rock type (and Pikachu's Thundershock doesn't affect). Brock was much harder. (I have nearly always started Charmander.)
Bugsy: His Metapod and Kakuna are too bad, they should evolve or something. Scyther is bad if it uses too much Fury Cutter but it could be a couple of level better.
Whitney: She has better pokémon, Clefairy isn't so bad (but it has Metronome!) Miltank is good because it has Milk Drink and Rollout (I died so many times when I first time played Gold) but that Miltank has weak point too. It's very easy to win with Geodude. Whitney was good in G/S/C but if their going to increase other levels they have to give some levels to her too.
Morty: He's better too, Gengar is good pokémon, because it has Hypnosis and Dream Eater. Gastly and Haunters aren't so bad, because they use Curse. I think Morty is bad in HeartGold and SoulSilver because I have always won him with my Geodude's/Graveler's Magnitude, and now those ghosts has Levitate. I think Morty could be very hard to win in HG/SS.
Chuck: He's hard with Cyndaquil as starter. You can't get many electric pokémon from beginning but I beat him with Pidgeotto (yesterday I beat him with Weepinbell). His Poliwrath is good pokémon, it has Hypnosis and Dynamicpunch. And if you have Fire or Rock pokémon he uses Surf! (I think, Surf is best battle HM.) His Primeape isn't so bad, it is dead after one second.
Jasmine: They should make another Magnemite to evolve, because those are too easy to win. (Quilava Ember! Magnemite fainted!) Steelix has good level, but it's easy to win with Graveler and Quilava. This Gym Leader is first who has Potion, every other Gym Leaders needs Potion too and I think they have in HG/SS.
Pryce: Not much to say. Too easy with Quilava/Typhlosion but I don't know about other Starters...
Clair: Hard Gym Leader, finally! This one is much better than others. She's Kingdra is good pokémon (You can't beat it with Fire Starter and there isn't much Electric types in whole game). Dragonair's are good too, this Gym Leader needs always another battle in Gold, I can't beat her with my low leveled pokémons. (Wild pokémons are too low leveled, near Lake of Rage today: "Pidgeotto lvl 17... This is too easy... And what's that? This Trainer has only 18lvl Nidoking?)
Elite Four: Elite four is little too easy but I don't write about it so much.
Will: is hard with Cyndaquil as Starter. We need electric pokémon!
Koga: This one is easy with every pokémon... Needs levels.
Bruno: Easy too. You need only Water and Bird pokémon with you.
Karen: Too easy. I can beat her almost in 3 min with low leveled pokémon.
Lance: is good with his dragons. Has Fire, Water and Rock pokémon too, it makes him much better. But when we look at his Dragonite's level... It's only lvl50... It could be little better...
Kanto Gym Leaders: Every of these are too easy to win because you can use your good pokémon from Johto, but if you make them better by increasing levels, Red has almost lvl100 pokémons!
I think you guys don't like this text but...:
So, two regions has it's bad sides too... But why can you use your best pokémon in Kanto. I think it's better to leave you're good leveled pokémon to Box. In Johto you need Badges to make you're pokémon better leveled but in Kanto you need those only for Mount Silver. I think there could be man who says: "You can't come to Kanto with those pokémon, you need to pick lower level pokémons so you can come to here". Then Kanto Gym Leaders could have lower leveled pokémon and you have those too. When you're battling against Red, he hasn't 100lvl Pikachu and you have good leveled pokémon that you have caught from Johto and from Kanto and leveled in there.
Much text... I hope someone reads this, I used time to write this...