Some things I think would be cool:

1. Private commerce space vehicles. Once you build a trade port, let there be private enterprise ships that don't travel the normal space lanes. Like say a chartered flight to go sight seeing in a nebula or star or a private cargo run. Have them automatically have a bounty on them (so they have value to other players - like hostage or cargo value).

Have attacking and destroying them not cause war but maybe drop relations a little. This would make the world more dynamic, inter-'national' incidents more frequent, etc.

2. Have smuggler craft and that show up in your systems that you can interdict (or other players can too). Have them be pirate faction or whatnot. With a bounty so there is a reward for policing your system.

3. Random events. Don't have to be big game modifying (in fact they should all be fairly minor, no one should win the game just through random events imo).

4. Upgrades to engines. Seems really weird to me that ships never get faster in the game (except jumps if you get the artifact).

5. Some sort of researchable civic ability to increase tax rates. Maybe a tax slider ala MOO2 that reduces production speed or reduces system happyness.

6. Morale that means something. Make flexible tax rates to encourage growth in remote systems and keep morale high. Or increase taxes with a greater risk of system revolt or whatnot.

7. I guess it might be beyond the scope of this game, but I think it would be really cool to be able to customize your own ships as far as armor, weapons, engines, shield generators, etc.

8. Much as others have said, Diplomacy is a mystery. How well do I get along with the AI? Where do I stand? It would be cool to lend/lease ships to the AI temporarily to help him out, or let him do the same. This could be pretty cool for multi-player games as well.

9. Ship damage. When damage goes through shields, how about a change that weapon systems or engines or something get damaged? Seems unrealistic that my 1/3000 capital ship is fully functional.