I didn't see this when I posted my thread (
http://www.lucasforums.com/showthread.php?s=&threadid=145796), but my thread is more about randomly generated maps, so no damage done, I hope.
Yes, there should be deep space. Interdictors can, as was said, still intercept ships, and would, as stated, get an added field of use as they'd prevent fleets to get from point A to point B, rather than just trapping them in combat. And when they intercept, they engage their projectors and the enemy fleet is stuck. Just enable a "patrol" command like the defensive stance of soldiers in RTS games to have it and its fleet move automatically to enemies they see. Also, you can place the planets far enough apart that it'll take more than a turn getting there, enabling the enemy to spot the fleet and order an intercept manually.
Alternatively, or additionally, give it a range for its gravity well projectors. "Any ships within this circle can't move!" Probably not a good idea, though, as it'd be very easily exploited if you put an interdictor near a planet and thus stranded the planet's fleet without the said fleet being able to catch you... Come to think of it, nothing would be able to catch the Interdictor if they couldn't move towards it. Scratch the latter idea:p .:o
In Stars! you could even lay mine fields (which covered a circle-shaped area). Mines could only be traversed at a set speed - faster than that and you were screwed. Thus, if you gave a ship the order to go from here to there at Warp 8 and entered a Warp 4 field you didn't know about... Boom. "Fleet #7 has been disintegrated in an Insectoid mine field.":eek: Don't think it'd fit for EaW, but maybe asteroid fields working the same way would?
PS:Just in case someone's interested, it was nicely implemented in Stars! (which is also discussed in my Random Map generator thread).
Ships move together as fleets, shown as icons on the map. They either orbit planets or are in deep space (either alone or with another fleet). You move them by right-clicking on the map after selecting them. If your cursor is close enough to a planet or fleet, it "locks onto" it so that you won't accidentally order your fleet to move a millimeter off of it (planets were represented by dots, you see;)). A window in the UI showed speed, fuel consumption, and ETA and let you change speed. Lines showed you where your fleets were coming from and where they were going, or, for enemy ships, just their speed and bearing (the line never started or ended, but you could assume where the fleet had come from and where it was headed to by following the line and seeing if it intersected anything). Battles start if fleets meet enemy fleets or reaches an enemy planet with a fleet or starbase. Fleets at the same place can transfer fuel, troops/colonists, cargo, and merge with each others (fleets can also freely split). Then you can queue up things and tell a ship to "go here and pick up minerals, return and unload them, then repeat the process", or "meet with this fleet and give it all your cargo, then move to this planet and lay mines for 2 turns". I have a feeling EaW won't be this complicated;), but it was a neat system.