First Level As Tutorial...
I'm a big fan of the first level functioning as a "natural" tutorial, where the player is introduced to concepts in a gradual way, but the level is a real level that's part of the character's mission/story, and not some "training room" where you shoot mannequins.
Some examples from games:
Quake 3's entire first episode was sort of a tutorial where they start out with a tiny flat map with no loops (and a teleporter tutorial), and slowly add loops and overlapping paths etc. in the subsequent maps.
Metroid 1 started with the player trapped in a small 6-7 screen corridoor, where they cannot progress without collecing the "round ball" item so that they can roll through a narrow gap. This teaches you that that the game scrolls both left and right (unlike previous games like super mario brothers) and a introduces the concept of items opening up access to new areas. As soon as you get the round ball you can't even leave that screen without using it to roll under a large obstacle.
The first level
of Prince of Persia teaches you about false floors in the very first screen -- you can't even leave the screen without triggering it, and they force you to drop down onto the lower part of the screen, which causes the floor panel to rattle a little, helping to show you it's there. The third screen teaches you about pressure plates that open up doors.
I realize this is a bit of a derail since the thread is actually about making a good impression / hooking the player in the first level.