As long as they're successfully able to integrate a story through a procedurally generated universe, I don't see why any of this wouldn't be possible. I mean, it doesn't even have to be the size of No Man's Sky (that's asking a bit much), it could just be extremely large. It'd essentially take on a galactic GTA kind of feel (as far as missions, side missions, exploration).
Say, they have layers of story lines. There's the initial one, and then there are additional stories that unfold as you explore space. You come across new civilizations, or fledgling/primitive life forms etc.. It's doable, but they'd have to find a happy medium between forcing people to explore vast regions of space, and the discovery of a new story line.







