The problem, and I believe there is a problem, is more nuanced than I think most people give it credit for. The 'facts' somewhat change depending on the skill of the player involved. Do legendaries make your deck better than your opponents? The answer is not a simple yes or no. The real answer is: The better you are at the game the less the rarity of your cards relative to your opponent's matter.
And so you get strong players who will say legendary cards aren't better and so forth. And they aren't lying per say, but it also isn't strictly true when the game is being played at a low rank. When you're new to the game, you rely on the quality of your cards much more strongly. And because of this, one player having tirion and the other having nothing is a big deal.
But I think most of the people who do in fact see this as a problem are approaching the solution from the wrong direction. Measuring the 'strength' of a deck based on rarity or dust or anything like that is flawed. And the reason is because, as I said above, the strength of the cards in a deck changes dynamically based on the skill of the player and the synergy of their deck.
The real problem, as I see it, is this: Players who are new to the game are generally not going to create decks with a honed, well designed game plan. They both don't have the experience to even know how to make a top deck like that nor do they have all the very specific cards needed to make that happen.
Instead, they are going to make decks by throwing in cards that they generally think are good cards. Doing this will result in some kind of value/control deck. And they're going to get faced against people making their own value/control deck. And in these matchups, one player having legendaries while the other doesn't will strongly swing the game.
Why? Because a value/control deck needs strong end-game cards to complement it. And for whatever reason blizzard decided not to include strong common cards in the 6-10 mana slot.
At 6 you get boulderfist ogre plus some mediocre cards. At 7 you get stormwind champion which is... okish. And 8-10 nothing. This means that someone just making a value deck with generally good cards tops out at 6 mana. And when their opponent has access to 7-10 mana cards for their decks and their opponent doesn't that is a large handicap.
But the solution isn't to try and come up with some complicated match making that won't end up working anyway. The solution is to introduce powerful common minions in the 6 - 10 mana range that are on a powerful level equivalent with rag and ysera. We see this already with Boulderfist Ogre. Sure, given the option most people would play Cairne over Ogre but they really are quite comparable and there are many situations where Ogre is better. And I think even top players would be surprised at how effective Ogre would be if they would just swap Cairne for Ogre and play a few games. He's not complicated or 'cool' he is just a solid powerful card.
I believe that if you introduced new high end common cards a lot of the perceived problems would lessen because new players feel like they're only 40 dust away from a card that can compete at that level.
When people complain about being f2p and the cards they can't deal with they aren't talking about lorewalker cho, tinkmaster, or millhouse manastorm. They're probably not even talking about Harrison Jones or Black Knight. They're talking about Rag, Ysera, Alextrasa, Tirion, and so forth. And the very legitimate reason they are complaining is because there aren't any cards at that power level they are allowed to play. I see it as a flaw in Blizzard's design that there aren't comparable common cards at that level for new players to play with. But it is one that is readily fixable with the next expansion of cards.
