The novelty was the story in FPS.

For me Unreal already filled that place. Of course HL amped it up to 11, but Unreal already had decent story elements for that time. I loved how you could track the fate of fellow survivors over multiple levels at several occasions. The lore strewn around. Reading the log of a guard who you just blew to smithereens and finding out they were handed a crap posting, making you almost feel sorry for him.

The way and scale of how HL handed the story was absolutely novel and definitely something else, but it most definitely wasn’t the first to include story elements.

Before Half Life, all you have to do is to shoot every moving sprite and grab keys to open doors.

Most definitely not true. 1997’s MDK springs to mind and the before mentioned Unreal also had nothing to do ‘with shooting sprites and collecting keys’.