Ok, a few things to improve 'epic playability' in the game then, compiled from posts so far:
1. AI needs to be is an actual opponent, not merely a designed obstacle. AI should actively see other players as opponents, and should actively pursue a victory condition that they see they can most likely achieve.
2. AI should not be push-overs in diplomacy. Make it much harder to manipulate and bribe AI's to do your every wish. Example: get rid of trading influence points (adds nothing but abuse to the game), keep trades fair, but add elements of 'difference'... such as Friendly civ's will trade more fairly with you, civ's that don't like you will want more for less... depending on how a civ 'feels' at the current moment, it may be more giving or less giving... just to randomize things up a bit, make it tougher to make AI's go to war with everyone, taking whole 'PLANETS' and 'STAR SYSTEMS' from the AI for crappy techs.
3. A "Corruption" Model. To avoid runaway games, some sort of small penalty should apply to having excessive amounts of planets, although nothing as extreme as Civ3 was. In reality, research would be slightly slowed due to planets lightyears apart needing to coordinate their efforts on a single goal. Fraud and corruption are real things, and economics should see a slight decrease when empires become very large. Production, though I would say should stay as is, since workers don't slack off because they live in a large powerful empire, although perhaps an ever so slight decrease due to the logistics needed for transportation of supplies throughout an empire.
4. Enhance AI's ability to build social improvements in a more intelligent manner. If each AI assigned itself a long-term goal, say every 20 turns or less, on what victory condition it felt it was best able to achieve, it could follow a planet building / re-building scheme appropriate to best achieve that goal. If it is research, AI builds more labs. If it is military, it builds more factories. If it is diplomacy, it builds better relations. If it is influence, more culture centers. If the AI is running low on funds, build more econ buildings. This would make an enormous difference in gameplay. I'm confident that Stardock will take care of this though. Probably doesn't even need to be mentioned.
5. Tech's that become known by more civilizations, become cheaper to research. If all civ's know a tech except for one, then it would be a relatively cheap tech to research. If you are the first civ to research a tech, then research time is full price.
6. Enhance AI's ability to create better units. Perhaps base it on an algorithm that states: a Civ's high production planets will produce best possible ships, mid production will produce good ships, low production will produce cheap ships. Simple, yet effective... and more human like, since I'm sure most players don't build ships on low production planets if it takes 168 turns to complete. AI could evaluate current and potential enemies, their weapons and defenses, and have the ability to more quickly change their designs.
7. Change the fact that the Attacker always has the advantage. If all things are equal, defenders should have the advantage, due to familiarity of their area, better tactics due to being in their space and developed defense plans, better logistical support.... If they add ship classes to the game, where various classes have different advantages, some specialize in defense, others in offense, and the AI builds them appropriately, it would create more of an epic feel. Taking a planet would be "Finally! I took Epsilon Eridani III! Tough, but worth it!" other than how it is now "Took another planet, only 56 planets in the universe left".
8. Having 'Ship Classes' would emphasis the tactical use of ships of all hull-sizes (many ideas have been given about this, and are all terrific ideas). Making a small-hull a Fighter class would give it an attack advantage. Small-hulls that are Defender class get defense bonus. Corvette class would be a mix of both and specialize against Fighter class. Assist class Medium hulls can assist other ships speed, weapons and defense. Escort class get improved offense and defense when escorting certain types of ships. Similar to how many games of this type are... it would add a great amount of tactical variety to the game.
9. Add various Space Terrain... after all it is a galaxy, which would include nebula, matter outflows, globule's, clusters, various galactic medium, debris discs, stellar bands rings and trails, voids, magnetic fields, radiation fields, filaments, walls, stellar winds, galactic bubbles, nova, jets. Probably wouldn't need too many, so the map isn't clustered, but these can give benefits or penalties to ships that enter them. Bonuses and Penalties could apply to Offensive weaponry, defenses, sensors, speed, damage to the ship, and could also give various other bonuses (similar to how anamolies do now) at random. This would add more tactics to come into play, and would make flying through space a little more interesting.
10. Tech tree research priorities. Don't even need to mention it, tech tree will most likely be massively overhauled by Stardock anyway for GC3. Hopefully they optimize the whole system, to keep play a little more balanced between all civ's in the game. If the AI can research tech's that it needs to survives, this would improve play ten-fold. This way, it can actually be the 'best' player that wins.
11. Enhanced AI ability to estimate it's opponents abilities and act accordingly.
12. Disrupt opponent's Economics, Research, and Production. In most similar games (civ4 for example) you can disrupt a city's production by destroying improvements. This cannot be done in GC3 to any extent that really makes a difference. Only spies can actually do this and cause big problems. I agree with hairlessOrphan, More options are needed for attacking or undermining someone else's economy, research and production, in and out of war. Space bombardment has said it will never be used, so planetary bombardment is out of the question.
13. Make it harder for the player who is far ahead. Once your ahead, it gets EASIER to get way way ahead. I agree, and something should be implemented to make this not so easy. Numbers 3 and 5 in this list are a couple ways to help accomplish this. Also, all civ's should become more way more aggressive towards the civ that has a large lead. Of course this will only happen if they make the AI an opponent, and not simply an obstacle.
13. More realisitc diplomacy. More realistic actions from the AI due to breaking alliances, surprise attacks, and betrayal. AI's should become untrusting of anyone who 'screws them over' for a while at least.
14. Well, that's it for now
If GC3 has alot of these things implemented to some extent, it would make beating Tough difficulty seem like Suicidal is now!