Plot != story.
Nobody, not even Bungie, has any illusions about Halo having some brilliantly original plot arc. The influence of numerous scifi classics is obvious and acknowledged - and hell, half of the plot and characters themselves are thinly-disguised variants of elements from Bungie’s own Marathon series.
What set Halo’s story apart was in how it was told, and the setting in which it was placed. The art design and music of Halo was revolutionary for FPS games of the time, shying away from the usual post-apocalyptic brown corridors and heavy metal soundtracks and embracing a bright, outdoor color palette and a nontraditional textural soundtrack that changed dynamically with the player’s actions (often dropping out completely during the numerous quiet moments in the game).
Importantly, Halo 1’s level design also emphasized exploration over rapid plot progression. Its wide open spaces and ludicrous levels of background detail rewarded players who wandered around rather than making a beeline to the next objective marker, and reinforced the primary atmosphere of the game - that of being lost and alone on a massive alien construct.
The second level of the game, “Halo,” is probably the best example of what I’m talking about, as you’re tasked simply with “finding a bunch of Marines,” and then dropped onto a giant outdoor environment with little idea of what that means. Though the game does provide suitable markers so you never actually get lost, the vastness of the space makes it feel like a real place, rather than a “level” constructed by a game designer. Afterward, when you first drive your Warthog underground into the Forerunner facility for the first time, you actually feel like you’re discovering something strange and ancient, rather than simply moving on to “stage 2” of the level.
That verisimilitude is something that Halo 2 and 3 lost, in my opinion - and which Halo ODST seems to have revived, to a certain extent (although ODST shares Halo 2 and 3’s terrible dialogue).