Seeing that C-Evo (www.c-evo.org
) is on the list, I feel I have to advertise it. It is a Civ2-like game that is purely deterministic - that is, except for a map, nothing is random. While it does not have very flashy graphics, and the rules take a short while to learn, it is just wonderful. The best thing is that the rules are very well balanced, and few enough that one can actually keep them all in one's head, and know exactly why things happen. It is also one of the few programs I know that seem to have no bugs at all.
The only trouble is that it is pretty hard.