...did you ever play Marathon? It's gameplay was nothing at all like Halo's...while Halo was sort of a run and gun with strategic elements, Marathon was almost a first person RPG, in that there were very few enemies and it was really driven by your interaction with the terminals...
now, imagine the terminals actually talk to you, instead of you just having to read them, and add a leveling system for your character as you go along, with the same kind of frantic multiplayer that inspired Halo's, and you have a crazy cool new game that's very different from Halo.