http://neurohack.com/anacreon/
Anacreon - an ancient 4X game (originally in ASCII!) which had artificial world construction, "spice worlds", and lots of other cool stuff, probably long before the genre was even called 4X
edit: oh, and let's not forget Star Lords, a prototype for Master of Orion! This game was actually released as freeware a while back...
http://moo3.quicksilver.com/game/starlords.html