http://www.youtube.com/watch?v=8FpigqfcvlM

Thought this was interesting.The commentator demonstrates how the Megaman games through their level design taught the player how to play without an explicit tutorial.

This technique seems to also be done by Valve, especially in Portal. If you listen to the developer commentaries in Portal you'll learn how they've designed the levels to lead the player. Teaching the player how to use momentum to reach places in particular stuck out as something they've designed levels for.

The first level of Super Mario Bros is basically this.

it's funny, despite being older than him MX4 was all that MMX1 was to him.

though command mission had the best opening:
http://www.youtube.com/watch?v=1C2iomx0Clg&feature=related

Nice, though here I was talking about opening levels.

Hahaha, I clicked the link and a Pepto Bismol ad came up that featured Santa's elves in a dramatic scene on a shrimping boat.

Oh, yeah, the video was cool too. If a little over-edited (okay, a lot over-edited).