It is impossible to overstate just how astounding Doom was when it was released. I had heard people talking about Doom for a few weeks but didn't know anyone with a fast enough PC to actually run it. Then I found that a friend of a friend with a 486DX had gotten a copy from somewhere so we all went around to see it.
Your description is exactly correct. I still remember the amazement when we realized that you could go up the stairs. Managing to find the secret doors and actually go outside elicited gasps.
I am not sure that Dooms level design has ever been beaten in terms of how elements are introduced to the player.