I have a slightly ironic question to ask, given my position on exploration: why do you feel that exploration does have to be included?
1) Players will complain that it's 3X and not 4X OK, that one is minor and not so important, still worth to mention.
2) Information overload. If there are 100-200 systems I do not want to know details about every single one from the start. It will burn my mind with computation requests. I prefer this information to be given to me in chunks over time.
3) It's hidden information and surprise. Let's face it, strategies are pretty predictable games. You know the tech tree, you more or less know possible enemy races, you know the buildings, you know what ships you will design. An unknown (or partially unknown) map is great because you don't know a lot of critical factors from the start (enemies placement, good planets placement, space lanes between planets/systems).
4) Replayability. Sure, you could say if the map is random and you see it from the start it's the same replayability. But I don't think so Hidden map is, well, hidden. Even if you ended up on a similar map next time you play, you will not know it till the end and will still enjoy it and be on your toes.
5) Ancient ruins, artifacts, anomalies, singularities - these are great, but... only if given successively on the way, not all at once (I would be unable to even read all their descriptions if these were revealed at the start!)
So... I don't like exploration on its own, but it has many benefits to the game as a whole (replayability, hidden information, dosage of rewards, prevents infodump, etc)
What does your game look like if you simply drop exploration entirely: all planets are already known to the player (via starmap, scanner and database)?
Perhaps think about the elements that you love in space strategy games, and put some thought into making those elements the core of the experience.
I like the way you think
Actually, I wouldn't mind to give much more information about the map from the start (for the particular game I'm making, overall it would be bad I guess) and/or grant cheap/early exploration. But still... if nothing else, the info overload is unacceptable (I would need to really simplify these planets). Also, some information should be revealed later (OK, I could use events for this, but... come on, digging out an ancient artifact from a planet is far more cool )
I definitely don't want to make exploration the core experience (I don't like it THAT much), yet, I like it enough (I suppose) to include it... I think Unless there is an important reason to exclude it, I could go for it then