Yes, you need legendary cards to have a deck with legendaries in it. Oh also, Control Warrior and Handlock are fun decks, and they have legendaries in them to construct, so you need them to run those decks.

But what about many types of mill decks? Many aggro decks? Many zoo decks? Tempo decks? Hell even ramp druid doesn't need legendaries.

Yes you can't have your cake AND eat it too. You can achieve the highest rank in Hearthstone with multiple decks without spending a dime on the game. And the arena is self sufficient with ability. Asking more of that from a card game is insane. I'm sorry if that's boring and repetitive.