[edit]Uh, forgot: I'm talking about PN03, not Halo here

[/edit]
Well, just finished it. Clocked 4 hours-something on easy difficulty. Remember, that's really easy, so you'll finish all levels on first try (as opposed to 5-10th) and often without losing a life. Once you finish you can start over with all your stuff but no points. So be sure to shop a lot before ending the game. Don't worry, your boss will tell you when you reach the last mission.
I finally found the story! It started in level 9 and the game ended a few missions later. They could have spread out the story a bit and go into more detail easily. The story turns were about 70% what I expected, but they give the whole thing a nice atmosphere not unlike what you feel at the end of "The Cube". Yes, I refer to that movie pretty often because it had the most atmosphere I ever saw in a movie.
The environments really don't get that repetitive. They of course repeat when you are in the same location and some room styles get reused (very few and always with different enemy spawns). Most levels have distinctive designs, though and the only similarity throughout the game is the color style. Mostly grey, sometimes a little brown in between, but all in all this just seems to serve the atmosphere.
What I didn't like was how easily bosses get killed with your specials. Heck, even the last one needed no more than 4 super attacks (though those 4 were all my energy could deliver). I hope this changes with the higher difficulties.
Also I think the game should keep track of highscores, not just give you a rank at the end of the game.