The thing I love about the marathon series is that there are no cutscenes - everything either plays out in real-time or you read about what happened afterwards, but it's still from your own perspective. You never really know what the AIs or anyone else is thinking, and you're left to deduce what's going on from the bits and pieces you can collect.
I also really enjoy that there's a reason you're there, a reason for what you're doing, and what you're doing is really quite clever (like in marathon 1, there's a part where you're closing airlock doors so that Leela can depressurize that entire section of the ship to kill a ton of Pfhor). In halo, the answer to everything seems to be having the master chief personally murder every last enemy - in Marathon, there's absolutely no way you can do that, so the AIs think of workarounds and ways that you can kill a bunch of them indirectly.
Also, I love the BOBs in M2 and Moo :<
Also, yes, you get the assault rifle in waterloo waterpark. You go down the opposite stairwell from the one that leads to the room with the pool of water and the chip.
Also, yes, the story is uncannily deep and excellent.
http://marathon.bungie.org/Story/