There were several games created in that fashion around that time, fortunately, I believe you are looking for what is known as a 4X Strategy game. Here is a list, I would be surprised if your selection is not on there http://en.wikipedia.org/wiki/Chronology_of_4X_video_gam... . If you simply think you'd like a good 4x strategy from that period, I would recommend Masters of Magic, it is available on GOG.com and has a decent following, there are mods pursuing multiplayer and also some that up the difficulty/"realism"/makes some spells that were formerly useless less useless.
Civ2 was an extremely popular one around that point too, released in 1996. 4x games are some of my favorite, I recommend anything by Microprose, or Simtex I believe made the Master of Orion series.
I'm having fun playing it.. feels like a completely different game now that I have actually gotten my hands on it again.
Makes me think of the saying that goes "thinking about it was better than having it" or about Nostalgia..