An oldie (1995!) that I was thinking about today: Millenia: Altered Destinies.
Distilled down to its core, I'd say it's resource management and order puzzle... but that really trims it to bare concepts.
You're basically flung into an alternate galaxy in a time travelling spaceship with the mission to arrange the galaxy such that the four sentient races each dominate a quarter of the galaxy *and* can defeat the invading alien threat, or just find a way home by letting the four races take over the galaxy in turn, steal their tech, and leave (with the implication that our galaxy is next to be taken over, in a few thousand years time).
There are pretty finite resources; hopping to each planet to talk to them takes fuel, as does time travel, and refulling has pretty good odds of damaging your ship. Different races need different technologies at different times to develop further (which is manifested as a physical item that you take and give), and once they become spacefaring, they'll also go to war against each other, compounding your headache. And on top of all this, you're not the only one mucking about the timestream in this galaxy; you'll occasionally run into alternate versions of yourself undoing your hard work.
And, for extra fun: With how much of this game is partially randomized, it is VERY possible to have an unwinnable galaxy, either through bad placement of your ambassadors, screwing up technological developments, or just running out of time, that you won't notice until you've sunk like 20 hours into it.