for item 1: hmm i don't know...Diablo 2 with each map beginning as "here are the borders of a procedurally generated map...contents unknown" is so classic.
thinking out loud:
How about "unknown planet" here, "sun there", "unknown thing there" icons to help when uncovering the fog of war?
Wait...or you are talking more about the inter-system linkages? I.e. you want to know the galaxy shape in order to lesson the navigation chore? I can understand that in some way....though...in X3: Litcubes Universe or Mayhem mod...some of the "the galaxy is a mystery" fun diminished for me once I mapped all the gates and systems.