Although the FPS had been around since the '70s, Wolfenstein 3D is the game that most people (old enough) can point to being their first real experience with the genre. The game is also remembered for being one of the earlier instances of censorship, as it was banned in Germany for its non-educational use of swastika and Nazi music. As for the next time we'll re-return to castle Wolfenstein? The last we heard it's supposed to be later this year.
Update: Wait, it's 2008? So much for celebrating its quinceañera.