Ok heres some of my ideas:
At the start of the game, you are introduced to your character on planet Earth, and choose a profession or "class" to be throughout the game. The story then evolves around your character being picked to colonise another planet/moon of your choosing and off you go. Once there, the action need not kick off straight away, it could be a slow burner. It may not nescesarily even be the Aliens as we know them to begin with. Remember Hudsons line "....or just another bug-hunt"?, to me that implied that occasionally, other problems were encountered and dealt with by the Marines.
I remember playing a game called "Shenmue" on the Dreamcast years ago, and a good part of that game was actually living the characters life until the story advanced by doing things like going to work for 3 in-game days before anything happened, but it was done in a way that wasn't boring at all!! (even though it sounds it!).
Once the "proper" Aliens appear, the story then branches off in whatever direction you choose. Do you join the Marines and go from planet to planet hunting them down? do you choose to stay behind with your colony to protect them? The possibilities are endless, as long as they make it BIG. A Mass Effect kind of thing is what would be needed to make the game work IMO.
Thats just my two cents anyways.