There were a lot of FPS with story on them, like Hexen (I and II), System Shock, Ultima Underworld (although it was more of an RPG hybrid, Outlaws, Unreal, Witchaven 2, Goldeneye, Duke Nukem 3D, Blood, Rainbow Six, Dark Forces, etc..

A lot of these had complex puzzles beyond shooting everything and colored keys, but also cutscenes, character classes, convoluted stories and extensive lore. Hell, Marathon and Marathon Durandal had incredibly complex stories and lore for what they where.

The biggest difference was that HL was a story without cuts where there weren't "levels" nor cutscenes, but scripted sequences to push forward the story.
There were though "chapters" but the change between these was minimal. It was the closest to a cinematic feeling we had to the date.