[handrous]

There's also the idea of the tutorial level masquerading as a regular level, so it doesn't feel like a tutorial. Earliest example I know of is Super Mario Brothers 1:1, but it may not be the first. It's distinct from simply ramping up difficulty, because it involves things like deliberately presenting challenges & opportunities in a certain order, and, at first, in isolation.

[EDIT] incidentally, here (many) games have an advantage over other software, because they play linearly rather than presenting a large space of possible actions all at once. Games that are more similar to productivity software (city builders, say, or grand strategy games) have trouble doing this without it being obvious that you're in a tutorial.

[dTal]

Portal was designed so that nearly the entire game was "the tutorial level". The gradual introduction of novel elements such as beams, turrets, and more advanced movement challenges kept up the interest, but it also had the hidden agenda of preparing the user for the climactic finale which brought all of those elements together.