Replayability? I think it's pretty high
Random map generation - only handcrafted levels are the prison (beginning/tutorial level) and the central hub + satellites (aka your base -- which you are free to customize moving furniture around). Actual item stashes are randomized in the whole game, so the content will always vary - this influences mostly what kind of resources you will find in each map, as for the most part you'll want to craft your items, rather than using what you will find.
The game itself is not linear at all, either. For practical intents and purposes it's "open-world", so to speak. There are several stations scattered through Mars, and you can explore them as you like. Worth noting that a particular location's difficulty is not set by the location itself, but by the infection progression, which goes up over time.
Your ultimate goal is to tech up your base, in order to fix the shuttle at the spaceport, and leave the planet. In order to tech up, you have to scavenge blueprints to improve each of the hub's substations.
Here you can see the map layout.
It's advisable to visit the 4 closest stations first, in whichever order you see fit, as the early tech upgrades (required for the later ones) are in them. Other than that, as I said, the visiting order is up to you. What I am doing myself was rush the 4 of them early on to gather as many tech blueprints as I could before the infection levels went high, and return later to those locations in order to scavenge raw materials. But in the end the strategy is up to you. It might even be viable to scavenge the chips from the further away locations first, before their infection rises to dangerous levels, and then do the closer ones. I'd not try it myself because I rely too much on my tier-2 tech to casually sacrifice it for that kind of rush.
There is also a survival aspect to the scavenging you carry out: In general the kind of things you scavenge are weapons (nice early on, not so good later on as most of the ones you find are tier 1 or 2, and you'll want to craft your own by mid game, which will be better), general stuff (which can be scrapped into raw resources), drugs of various types (from medikits to mutant plague antidotes, passing through performance enhacing drugs), and, crucially, food and water. Your character has to eat, drink, and sleep. And not all sources of food and water are equally safe.
Soo... I think I covered the basics with that. Anything else I can answer?
PD: The guys who made the game announced at the GoG forum that they would release a major update soon, which will include more story content (there IS a plot about what's going on... currently you learn about it mostly in the form of logs in your journal, and notes you find around).
THere was also talk about some other major content updates which would add new gameplay modes. They posted a roadmap about this on steam
Coop multiplayer - This is the biggest update and it will only happen if the game significantly does well because this kind of update will require many months of focused development.
Random map tile editor - This tool will let you create the room tiles that can be spawned during random map generation.
Alternative ending with West's personal story line - We already have done some work on this. This has a good chance of getting in the game through a free update.
More background stories and little sub missions that can enrich the game.
More background music. - We have some kind musicians working on this already.
UI scaling option for very high resolution.
Randomization of important key locations.
Randomization of all other ground floor levels except Central control and prison.
There are also other proposals with good odds of making it in, apparently:
https://trello.com/b/mUiBvLsZ/subterrain-post-release