The returns to skill on Brainstorm are vastly overstated by its proponents. While Brainstorm is an extremely versatile card, what to do with it is usually clear for the overwhelming majority of hand/game states. Demonic Tutor is a pretty versatile card too...you can grab any card in your deck! But in most cases the card to pluck from the pile is patently obvious.
Plus, it's silly to discuss the "skill levels" of cards, anyway. Cards aren't hard to play, decks and formats are. And looking at things from this level, Brainstorm tends to remove just as much, if not (in all likelihood) more "skill points" out of the format as it brings in. Consider:
-In a format without Brainstorm, deck construction becomes a much more interesting affair. Shells that rely upon cantrips don't have one clear best choice in Brainstorm, and have tougher decisions to make. Preordain versus Ponder is going to be a tough decision in many 75s, which often may depend on the meta. Decks that need a lot of cantrips are forced to dig deep into the back catalogue; oldies like
Portent and
Predict could become relevant, or a sly player's super secret tech. Currently, Brainstorm simply muscles them ot of the format...it's simply [i]so[/] much better than it's "peers".
Not to mention a lot of the more greedy manabases become untenable, forcing those playing archetypes like U/x/y Tempo to make the choice between more colors or more consistency.
-Discard actually becomes a serious factor in the metagame, forcing adaptation around it. Not only will players actually have to learn how to play around discard (in a ways that don't involve tapping an Island and putting two cards on top of their deck), but it makes deckbuilding, sideboarding, and metagaming more interesting. Players will be forced to consider anti-discard measures rather than having them as an auto-4-of in every deck with Blue.
-The ability to evaluate opening hands and mulligan becomes a much more important skill. Brainstorm allows for stupid keeps, as it can essentially swap out 3 cards in hand, making the art of the mulligan a less necessary discipline to train in.
All in all, Brainstorm's removal would make for a much more skill-intensive Legacy format than the current one, testing player's deckbuilding, metagaming, and play skills more than the one where 75% of the field jams 4x Swiss Army Spell into their lists without question. This argument is also a lot more concrete than one that maintains that because Brainstorm can do a lot of things, there are necessarily difficult decisions in a majority of situations; the stance adopted by many Brainstorm proponents.