OK, I'm going to indulge in some self-promotion here, but when did we first see a game use a first-person POV where you roam around a 3D landscape of mountains and valleys, fighting enemies with increasingly powerful weapons, and gathering your own weapons and defenses from the remains of past foes? Koronis Rift, 1985... Not exactly a FPS, but certainly a lot of the same basic elements.
-Noah Falstein, The Inspiracy
Alien Vs. Predator was the reason gamers bought the Jaguar, and it introduced a stack of gameplay innovations that we now take for granted. It was the first fully-texture mapped FPS on any console anywhere. It was the first game that allowed you to play three totally different and competing characters - Alien, Predator and Marine. It was the first game with vision modes. It was the first game based on a film licence that actually added to the licence, rather than just cashing in on it.
Aliens was the first game where gamers (playing as aliens) could run on walls and ceilings - something the marketing for Prey has recently made much of (seven years later!) Not only that but the AI aliens could run on the walls and ceilings too - making formidable targets. The damage system was amazing too. You could shoot off any alien's arms, even shoot off individual fingers! If you shot off an alien's leg, it would still crawl at you and try to attack you! There was never any respite from the aliens. Uniquely in any game, the aliens would track you down intelligently, so you could never afford to stay in one place for long.
It was the first FPS to have characters with emotions and different facial expressions. As the Predator, you could literally peg an enemy's head to the wall, and fire the homing disk which you'd have to retrieve if it got stuck in a wall. It was the first game to introduce three very different characters in multiplayer games - with a beautifully-balanced paper-scissors-stone gameplay.
The intensity was increased as you never quite knew what you'd find in a room before you entered it. No chance to play through using quicksave, die and reload techniques. You had to be a real gamer! One of my favorite special effects ever was the beautiful volume filling explosions - throw a grenade down a coridoor and watch the orange flameball whoosh out! I also loved the slow motion gameplay effects with accompanying doppler effect sound frequency shifting. All this well before Max Payne built a whole game on slow motion effects. A giant, multi-leap forward for the FPS genre!