Mech mage cards were generally low manacost, and they cheated out tempo using the mech warper. Piloted shredder and dr. boom were op. And, yeah, I wouldn't call the specifically tempo cards, just good strong cards.
Many C'thun cards have decent tempo because either of good statline or special effects.
There's only two C'thun cards I'd say fit this catagory. Unsurprisingly, they are the two that I've seen played in decks without C'thun. Cult Sorcerer, which, yes, I'd call an acceptable tempo card, or at least a card that fits in tempo decks. And dark Arakkoa, which I wouldn't call a tempo card simply because it's high mana cost prohibits it from taking the board control quickly. Otherwise, no. I don't think any of the other C'thun cards are actually good on their own. Often they are like... Kinda playable on their own? But not high tempo. Not good.
Flamewaker makes tempo from many small spells. Zoo makes tempo from minion synergies and the fact that they can go extreme with the low mana cost cards because of their hero power. Tempo paladin.... Well, it's a pretty aggro deck to call tempo, but, same idea as warlock, lots of tiny overwhelming cards and insane amounts of card draw. Where's C'thun getting equivalent tempo as any of these decks? The answer is simply that it's not generally. like, a C'thun deck might get lucky trades and draws and stuff and keep up, but that's not the point of the deck, and furthermore I'd have to stay that's not an average result.
Simply put, all these cards and decks you're using as examples have something the C'thun cards don't. Immediate high board impact for their cost.