Gnar is DESIGNED to be hard to catch in his mini form but easy in his mega. Rek'Sai is DESIGNED to have unprecedented mobility in the jungle, and to outpace opponents in open areas. They aren't impossible, they just take more effort than most single players can put out without gap closers or CC.
Gnar has a slow that he has constantly available on his Q in either form. His two stuns? Entirely situational. There's no guarantee that they'll be up during a teamfight, and if your team decides to engage when there's a Gnar who's about to go Mega it's YOUR fault for not waiting until he's either cooled off a bit more or wasted his transformation by backing away and playing defensively. Rek'Sai has one source of CC: knockups. Knockups which decrease in effectiveness the farther away you are, and aren't good for much besides BRIEFLY hindering a foe, or a few foes, while her teammates collapse in. Aside from that and increased vision in burrowed form, Gnar doesn't have a whole lot of utility. Just a fuckload of mobility.
Gnar's transformation isn't sustain. It's a bit of extra health temporarily. Rek'Sai has pretty healthy sustain, but it's not going to be taking her from half health to full off of just burning Fury, and if she's burnt all her Fury to heal up betwen fights her damage potential drops.
Both have insane base damage and good scaling? I'm sorry but no. Much of Gnar's kit is BONUS AD, meaning that early on he's not dealing a whole lot with it. Rek'Sai's early base damage off of her Qs, knockups, and burrowed Qs is meh at best, and her E is pretty abysmal even with true damage until significantly ranked up.
I don't see you complaining about Aatrox, Xin Xiao, Vi, Shyvana, Wukong, or any of the other champions who can win off of a nearly full offensive build with only one defensive item. Hell even Garen can do that. Anyone with a full offensive build save one item is going to be dealing a fuckload of damage while lasting juuuuust long enough to be too tough to kill without help.
Gnar's counterplay is knowing when to engage on him and when not to. If he's close to full fury, don't engage. If he's wasted his transformation, go in on him. If you're laning against him and you don't take someone with a solid gap closer to jump to him and hit him once or twice before he leaps away, punishing the squishiness of his mini form, that's your bad. He's highly susceptible to being bullied out of lane, even a Darius, a melee champ, can fuck him up early on. Darius' Apprehend range is longer than Gnar's AA range for most of the early game. When he comes in to get farm, E AA W A Q when he's walking away. Congrats, you just chunked him for almost half of his life and he's bleeding down to less than half. Rek'Sai? She can survive ganks if she's in lane by virtue of her tunneled vision, but her early game is still pretty weak due to relatively low base damage on her skills. In addition her main damaging ability pushes the lane, which means that she's losing CS while putting herself in an unfavorable position, more open to ganks. Again, shut her down early and she can't do a whole lot. This is also why she's better in the jungle than in lanes, because her early damage is admittedly very meh without itemization supporting it.