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
The reason the genre is called 4X is quite simply because when you pronounce the words Expand, Explore, Exploit and Exterminate the 'E' is silent and therefor was coined 4X.