I thought the story in itself wasn't particularly good. What made it stand out was the way the narrative was integrated into the game, instead of being developed through a cutscene or just written in the readme. It made you feel part of the story.
HL's story was only good when compared to the stories of previous mainstream FPSs (Doom, Quake, Duke Nukem 3D, and the like). For some reason, that prompted gaming journalists to say that HL had a great story.