I've started mucking around with Dwarf Fortress, which looks like a rather interesting RTS style game with a lot of hidden complexity. It's a difficult game to initially learn, so you'll probably want to read a tutorial about Dwarf Fortress.

To give you an idea of the world complexity, here's a pair of maps created with the Dwarf Fortress world generator. The tile set shown is the May Green graphical tile set. The first map is 550 years of simulated history before you embark your initial troop of dwarves, the second is 1050 years of simulated history. If you want to recreate these maps, I've provided the seed files that will work with v0.31.18 of Dwarf Fortress.

Dwarf Fortress v0.31.18 - Sample Map #1
See also: hi-res version (4112x4112) - seed file

Dwarf Fortress v0.31.18 - Sample Map #2
See also: hi-res version (4112x4112) - seed file

Reference Links:

FYDF - blog from 2010 about Dwarf Fortress
Smells like Dwarf Fortress - a graphical tale