Okay, my 2 cents on this.
When I look at the galaxy map, I want to see at one glance important information so I don't have to search for everything and look through each single planet.
First things first, remove the visible names of the planets. As I said in my other thread, make it that when you press "alt" you see the planet names. You don't need to see the names at all time anyway.
Second thing, coloring is important, especially in a large scale stratetgy game. We need to see what different factions control which sections of the map. Show the planets in the colors the player has chosen before the game, in my game this would be yellow for my planets, red for the AI. This makes it way easier for the player to distinguish the different regions. This is even more relevant when more than one players plays the game and each one has a different color.
Third, important structures. I liked the way how AIWC handled the map filters, you could search for specfici stuff like advanced research labs and other stuff. Problem with this was, you could use only one filter at the same time. My suggestion: Since this is an improvement from the first game, make checkboxes instead of single-filter search. That way the player can choose directly how many icons (and which ones) he want to see on the map.
Now, I also want to see warnings on the map (at all times but maybe we can make this also as checkbox filter). When the Ai attacks one of my planets I want a big colored warning triangle over the planet that is attacked. Yellow for planets that have an incoming wave warning. Red for planets that have currently enemy ships on them. Maybe we can differentiate even more on this but this should give a general direction for the player, so when he heres the warning sound and opens the galaxy map he sees immediately "Oh shit, these planets are on fire, better do soemthing about it".
Everything else does not really matter that much for me as long as the icons of multiple planets don't overlap and I can easily tell which icon belongs to which planet. This would probably mean, put more space between the different planets or make the planets/icons overall smaller. Generally speaking I don't think there will be a solution that makes everyone 100% happy simply because some players might simply play with so many planets, the map gets cluttered anyway. But we should aim for readability for the stndard setting (which is 80 planets if I rememeber correctly) and everything above is simply luxus.
