The game that halo most reminded me of was Oni, oddly enough.
Both were very very fun, but deeply flawed IMHO. Both featured some of the absolute best combat mechanics I've ever experienced, but the rest of the games seemed missing or partially finished.
For example, both games featured grand, epic architecture and settings that looked great but still seemed sort of half-finished and bland, with a lot of huge empty rooms devoid of detail and without apparent function. Essentially the levels were just cool environments to have fights in, and in Halo anyway every level was simply a string of connected fights leading to a cutscene. In Oni they were a string of connected fights interrupted by jumping puzzles :-P
Certainly Oni had a lot (I mean a lot) of jumping puzzles and find-the-switch type of puzzles which were pretty weak IMO, but which fit into the story well; after all, one of Konoko's defining traits was her acrobatic ability. Halo didn't even bother to have jumping puzzles, or any other puzzles of any kind that I can remember... it was really just fighting. Glorious, enjoyable, fulfilling, often laugh-out-loud-funny fighting, but still there wasn't much more going on beyond "walk from point A to point B, fight Covenant, continue to point C, fight Covenant, etc." Halo also had a surprising lack of possibilities for exploration, which is odd given the scale and grandeur of the settings.
The story and storytelling in both Halo and Oni was deeper and better than in most similar games, but not up to the level of the Marathon series on either count. I believe that the reliance on cutscenes and recorded dialog in Halo, and the inability to backtrack and re-read terminals in Oni made the storytelling feel more "spare", and to me anyway more forgettable. It also seemed easier to disregard entirely; I bet I could have played Halo with the sound off and still completed most of the missions without much trouble. There were probably far fewer lines of actual dialog and story exposition in Halo than there was terminal text in Marathon, and almost none of it was the sort of atmospheric or background text that was unrelated to the immediate game at hand, but which set the mood of the Marathon games so well. They seemed to have relied on the novels to set the backstory, and I'm way too much of a book snob to read a book based on a game ;-)
