So, the game I have in mind is a hero shooter, so either totally or mostly multiplayer, so really the premise is more important than a rigidly determined story.

But what I had an idea for is a fairly near-future game where mankind has started to try and expand outside our solar system, but after a series of high-profile accidents, the decision was made that national space agencies (such as NASA), were not to attempt to explore uncharted planets with manned missions. So, to fill the gap, a legal grey area was exploited (and supported by governments) to have privately owned companies send specialists (taken from prisons, the military, etc) down to chart the planets so manned missions are legal.

However, there's competition between the companies, and often they have subordinate goals to just having specialists explore the planets, so they come into conflict with each other. And out there in space, the law's a lot less enforceable

Honestly I do think it is pretty unique concept in itself, but would say you need a surprise twist, otherwise the game may become dull the longer it goes.

Perhaps the companies sent all the Marines, convicts there not only knowing they had to fight others from similar companies, but maybe this was the last planet government space programs sent manned missions too. Furthermore, the reason these missions were outlawed was because dangerous alien creatures or monsters inhabit it that decimated prior crews and threaten to wipe out humanity.
So perhaps the plot could evolve from fighting other companies, finding the wreckage of NASA settlements, solving the mystery, encountering a new threat, fighting them off and finding a way to block the new threat from reaching man.

Edit* Two other possible twist if don't want to go alien route. One could be that the Marines/convicts discover the corporations actually sabotaged the past space programs to get the contracts to explore space.

Another, perhaps instead of encountering alien creatures they encounter a virus that reanimates anything dead, including skeletons and severed limbs. Purge with fire scenario starts after the reanimated and twisted bodies of NASA crew wipe out most of the players company.

And maybe the expedition crews are mostly death sentence convicts that were reported to be executed, but bought and sold to corporations to conduct this work. Lead by a group of mercenaries or Marines as leaders.

Though, some plot may also mirror Red Faction to a bit, but also slight if any.

My two cents on it.