C'thun isn't that strong. The buff cards are pretty weak and just vanilla minions outside of the buff effect, so if you're losing early game control to it you're probably a bad player (uh, I mean unlucky). C'thun itself isn't too scary either as long as you have even a sliver of foresight and keeps removal for when they want to play it. Or drop a Sylvanas.
Basically, if you are losing to C'thun, you would've lost to everyone running big bomb finishers before this patch, because you're either not using the tools you are given or losing tempo to decks you shouldn't.