Halo has an epic BACKSTORY. It doesn't have a good story, but the universe and reasoning behind everything is pretty evocative.
That said, I really hope that The Conduit gives me a Perfect Dark sort of vibe in its single player. PD showed me that you could have a cheese sci-fi story, but it could be done really well. Well, maybe it wasn't cheese. The first mission in PD was a brilliant set-up for the Alexandra character, which pays off towards the end too. And play that mission again in Blonde mode... well... let's just say that I'd love PD to death even if there was no multiplayer for it.