Please implement something to teach players how to play

[Shurrikhan]

To the above, is the solution just to make the game more challenging then?

Honestly, yes.

The only real way to ensure the greatest coverage of learning is for said learning to seem inseparable from the game.

That's not an easy thing to follow up on, though. It requires well-crafted difficulty curves through careful situating of contexts and related actions, and it requires that those situations be engaging.

That said, the underlying idea to that, too, is rather simple: if you want people to learn your game, it needs to be a good game (and not just by its end).