Though I'm not a fan of every addition in Assassin's Creed 2, it is a lot of fun overall. In the beginning, it felt slow and confined. I knew that it would pick up and set me free eventually, but it definitely kept me on training wheels for far too long and held back much of what ultimately makes it a great game.
Learning curves make sense. It also makes sense that more complex games need longer learning curves.
But when your game has a lot to learn, the answer is not to restrict players to a little bit at a time. Rather, offer the player many options at any given time and restrict only how much is expected of the player by challenges he or she faces. Offer elite challenges, but only in such a way that they are clearly bonuses and not necessary to progress in core areas.
It's like teaching students. If one student is already somewhat familiar with a topic or picks it up quicker than other students, the solution is not to silence that student and prevent him from offering what he can, so that other students don't feel pressured. Instead, the solution is to allow that student to surpass normal requirements and provide special challenges that other students can happily skip and forget.
Players should never feel like they're held back... that they're offered too few options and opportunities. Players should never feel like they're waiting for "the real fun" to begin.
Making learning curves malleable enough to suit multiple playstyles and levels of experience should involve more tweaking of challenges and expectations than of opportunities.