I think nebulae and black holes should be visible from the start of the game, and should not have to be 'discovered.' I say this because even TODAY we can detect nebulae and black holes from Earth, without the fancy future technology in the game. We find black holes either by the gravitational effect they have on other celestial bodies, or when they distort light passing near them, creating cool effects like doubling images of stars behind the black hole. Nebulae are even easier, as many are visible with the naked eye or simple instruments.
I do not think making these visible is unbalancing... everyone will know where these features are, and their primary strategic value (i.e., presence of resources) will still be unknown until they are explored.
Note: I'm not sure if 'storms' should be visible... I am not sure they even exist as they are portrayed in the game.