There are certain small additions which I think would add fun to the game.  Not necessarily strategy, just fun and polish.

1) DARCA1213 mentioned that the stars look like marbles.  He's right.  Stars aren't just illuminated balls.  They are covered in fiery storms, sunspots, etc.  Give them character, as they are some of the main characters on your map.  Flares.  Binary systems.  Accretion disks.

2) When ships move, they shouldn't just slide across the map.  Different engine types should animate differently.  Rocket blast...  Ion burn...  Hover disks...  should shoot out the engine in the other direction.  Or perhaps the ship can spread out in the direction of travel as it bends space.  This is 21st century gaming.  Give the movement some character. 

3) As I mentioned on the other thread, I think some impassible terrain (up to a certain engine type) is a good idea to give the map some definition.