Everybody wants there to be strange alien artefacts/ruins/architecture hidden out there in the galaxy. Here is a proposal for a type of thing you could find: Crystal structures. By this, I mean regular 3 dimensional lattice-like structures.
The simplest example would be the cubic lattice:
WebGL rotatable model
(Cobra model from http://deephorizonindustries.com/griffind/Griff_Shipset_Resources_v1.2.25.zip)
This would either be floating in space, or partially embedded in an asteroid or planet. The lattices could be truly huge, with thousands or millions of "tiles". Occasionally, there might be much smaller alien structures hidden deep within, perhaps protected from asteroid impacts by the lattice.
Other good examples would be the molecular structure of diamond:
WebGL rotatable model
or the tessellation of space with tetrahedra and octahedra (as used in Escher's print "Flatworms"):
WebGL rotatable model
or the lattice known as (10,3)-a:
WebGL rotatable model
Why this is interesting:
The only downside I can see is that it might be difficult to produce good lower level-of-detail models for the lattice at distance. Possibly resolving an entire tile (or collection of tiles) into a cuboid/parallelipiped of the appropriate average colour would work well enough. There might be other tricks one could use to go further.
I have a few further ideas for mathematically inspired alien architecture, and will post more later. I am a postdoc research mathematician and mathematical artist in real life; my research is in 3-dimensional geometry and topology, and my artwork is mostly in the medium of 3d printing (see http://www.shapeways.com/shops/henryseg). So I can supply (pseudo or Python) code and 3d files (in .obj, .stl etc. formats) of any of these things if anyone is interested.
One further comment on point 2 above: In FE2, a scene in the intro has a ship flying through the arms of a space station. In FE2 this was never actually necessary. However, with complicated 3d geometry to fly around in ED, similar feats would be a real part of the game and would add an extra element of skill and interest in ship control and navigation at little extra development cost.
The simplest example would be the cubic lattice:

WebGL rotatable model
(Cobra model from http://deephorizonindustries.com/griffind/Griff_Shipset_Resources_v1.2.25.zip)
This would either be floating in space, or partially embedded in an asteroid or planet. The lattices could be truly huge, with thousands or millions of "tiles". Occasionally, there might be much smaller alien structures hidden deep within, perhaps protected from asteroid impacts by the lattice.
Other good examples would be the molecular structure of diamond:

WebGL rotatable model
or the tessellation of space with tetrahedra and octahedra (as used in Escher's print "Flatworms"):

WebGL rotatable model
or the lattice known as (10,3)-a:

WebGL rotatable model
Why this is interesting:
- These structures have mathematical/physical "purity", along the lines of the 2001 monolith and other structures we might imagine vastly superior alien civilisations would leave behind them as they transcend off to some higher form of existence. Their purpose would be mysterious: perhaps they are sensors, or used for some form of exotic communication system, resonating with gravitational waves etc. Perhaps they are something to do with witchspace (note that these lattices are the Euclidean versions of the structures seen in this proposal for witchspace).
- Exploring, navigating and fighting inside them would be very different from in open space or near asteroid fields or ship wreckage. Although confusing at first, the regularity of the lattices means that pilots will learn how to find their way. There are safe directions to fly through a lattice where the gaps between the edges line up, but a ship has to be careful changing direction and going down a new "passageway". It's similar to driving in Manhattan: you don't want to try going diagonally! Missiles will likely not be as useful as lasers in the confined spaces, and stalking an enemy will be very tense. How dangerous flying around in a lattice would be depends on the size of the lattice versus the ships. Smaller ships might be able to hide where larger ships dare not enter. Pirates might want to set up a base hidden within the difficult terrain.
- Lattices can be procedurally generated. Once you have the geometry for one repeating "tile" unit, all the other copies of it are, well, copies. The geometry for the repeating unit could even be generated from just the list of edges between "atoms" (the thickness of the lines could also vary between lattices). There are vast databases of real-world crystallographic structures that could be raided for this data. Also see http://en.wikipedia.org/wiki/Convex_uniform_honeycomb for yet more examples.
- Adding variety within a single lattice is also easy: just substitute out a tile for some variant, perhaps with some of the "windows" filled in, or the whole tile solid. Using these solid tiles, walls, mazes and other structures could be built within the lattice, or variation built in procedurally, Minecraft style. The boundary of the lattice need not be a cube; the data structure for a lattice can include empty space in tiles outside the lattice proper.
- In principle, collision detection between the lattice and other objects can be extremely efficient: First calculate the position of the object relative to the frame of reference of the lattice. From this we can read off which tile of the lattice the object is in, and then do standard collision detection against only the parts of the lattice in that tile (or likely, that tile and neighbours of it).
- Lattices can be drawn with very few polygons per tile, and still look good. The 2001 monolith only requires 6 quads or 12 triangles! These lattices can be drawn with similarly few polygons (24 triangles per tile for the cubic lattice, 24 per tile for diamond, 48 for the octahedron/tetrahedron lattice and 48 for the (10,3) lattice). For drawing enormous and complicated geometry, this is about as good as it gets in terms of polygon efficiency.
The only downside I can see is that it might be difficult to produce good lower level-of-detail models for the lattice at distance. Possibly resolving an entire tile (or collection of tiles) into a cuboid/parallelipiped of the appropriate average colour would work well enough. There might be other tricks one could use to go further.
I have a few further ideas for mathematically inspired alien architecture, and will post more later. I am a postdoc research mathematician and mathematical artist in real life; my research is in 3-dimensional geometry and topology, and my artwork is mostly in the medium of 3d printing (see http://www.shapeways.com/shops/henryseg). So I can supply (pseudo or Python) code and 3d files (in .obj, .stl etc. formats) of any of these things if anyone is interested.
One further comment on point 2 above: In FE2, a scene in the intro has a ship flying through the arms of a space station. In FE2 this was never actually necessary. However, with complicated 3d geometry to fly around in ED, similar feats would be a real part of the game and would add an extra element of skill and interest in ship control and navigation at little extra development cost.