The first things that came to mind were, 3-D, real-time, orbital bombardment, space carriers. In other words, "Sins of a Solar Empire". So....have to think of something else. Here's what I would do:
1) Separate out planet quality from planet size. One planet is Eden, but it's the size of the Moon. Another is a gas giant, but it's like Mars. Your dream planet is to find an Eden the size of a gas giant. Needless to say, the number of planet tiles would not be tied to PQ anymore, but size. Size and PQ both increase morale.
2) Much more variety and frequency of planetary bonus tiles. Let's see some 200%/300% influence tiles and 200%/300% morale tiles, 100%/200%/300% economic tiles (you build a stock market on them), planetary defense tiles, starship bonus tiles, ascension tiles (just like building an ascension starbase), any & all kinds of bonus tiles. Each planet should be unique, with a unique character--different size, different PQ, lots of different bonus tiles.
3) Lots of little events, all the time, and they sometimes involve ethical choices. Not just when you colonize a planet.
4) Ships orbiting a planet should be able to fleet up, same logistics, same everything; just like open space. This is stupid.
5) Planetary improvements which provide military assist, just like military starbases (except it only affects orbiting ships). Bonus tiles which boost those.
6) Special mining tiles, which act just like spices (or Uranium, or Oil...) in Civ3 and Civ4. Those are cool. They confer some small global bonus to your race, and if you have extra you can trade them, like a Trade Good. Some special tiles don't show up until you research certain techs (just like Civ). This may make you have to "upgrade' your Factory to a Mine, to get the bonus.
7) Lots more asteroids, and not always part of a solar system. This was cool in the campaign. Why are they not in the sandbox games?
8) Revamp the Espionage system, big-time. Although I don't know exactly how. Plenty of other people have strong opinions on that one.
9) An ability to beam food, or production, from planet-to-planet. Inefficiency penalties would apply. The penalties are usually significant, except for a select race or two. For them, that is their special ability: the ability to beam food & resources between planets with small penalties.
10) Bonus tiles even on PQ4 planets, and on terraformed tiles, and you can see them before you improve them. e.g. you see a 100% factory tile on your planet, but first you have to run Soil Improvement on it. It's a good motivator to do it.
11) Improvements to starbases which increase their radius of effect.
12) Starship bonuses should come in all the different forms: +25% missile, +25% armor, +25% hit points, +1/+2 speed, +5 parsec range, etc.. So red mining starbases would come in different kinds, ethical events conferring starship bonus come in different kinds, planet bonus tiles, etc. etc. etc.. It influences what kind of weapons/defenses you use.
13) Minor races should be obscenely strong, like the Dread Lords, but they just don't have expansionist ambitions beyond their own solar system. And they have their own unique ways of diplomacy/trading. Don't piss them off. Of course, sometimes there will be an event....
14) Trade should be significant again, like in Galciv1. They already nerfed economy starbase spam. Multiply the legal # of trade routes by 3X, i.e. Basic Trade starts with 10 trade routes, Master is 30. And require that the trading planets be unique combinations, i.e. not just 10 traders all going from Earth to Kora.
15) Economy/Influence starbase modules should exist which increase income--not just trade. I never understood why they didn't. Of course, income enhancers on an influence starbase have an interesting side effect: they benefit ALL planets in their sphere of influence. Not just your own planets.
16) Metaverse scores should be based on how soon you win, and they should factor in how tough your starting position is. Take an educated guess. If you start with a Precursor Mine on your home planet, nerf the Metaverse score. Not based on how much money/influence/research/starships you have at the end, or anything any joe schmo can do after the game's basically already won.
17) Let military starbases move one parsec/turn, like Terror Stars.
All told, if all these were put in, it would be a very different game.