Worth bearing in mind that AvP had most of its development prior to the release of Half-Life; nobody expected any kind of story in an FPS at that point. What little narrative connectivity the game has, was a last-minute decision on the part of Fox Interactive, as a response to HL's paradigm shift.
It's a bloody scary game with its total void of concessions to easy playability. Minimal saving ability, minimal cheating ability, extremely limited arsenal, enemies who massively outmatched you in at least one respect. And the sheer speed of it is daunting today, though this is more symptomatic of the snail's pace that 'realistic' shooters have conditioned us to.
I think it's a masterpiece of design, with each race having clearly defined strengths and weaknesses, and it's set a difficult benchmark for subsequent games to live up to.
That said, while it's scary, I don't feel it ever got under the skin of the characters. There's no cameraderie for the Marine, he's the standard loner FPS protagonist (which is a product of the time, rather than a design decision). The Alien's bullet speed and human-like fragility doesn't correspond with what we see in the movies (but it certainly makes them fun to play as/against). And any sense of the Predator's trophy hunting mentality is instilled by the player, rather than the game.
The legacy it really should have left was the sense of the game dynamic coming first in design, and of that incredible free-roaming AI which provided a different experience every time and forced the player to keep moving and alert. A lot of AvP's more brilliant ideas laid pretty much dormant until Valve mined them with Left 4 Dead many years later.
