idbeholdME: Master of Orion 2 is great. It's a pretty lightweight 4x game and I enjoyed it greatly. And I'm saying that as someone who usually finds 4x games boring/not my genre.
Master of Orion is a terrific game. Also in this vein,
Stars in Shadow is a modern game features a streamlined design that works. Fun and different. Really recommended (play the colonials first).
ConsulCaesar: Civilization IV is my most played game of all time. Many considered it the peak of the series because of its smart game design, with systems that interact with each other in ways that might not seem obvious in the beginning, but slowly reveal themselves as one gets more familiar with the game, but which can be safely ignored by a beginner. New players can start with the lowest difficulty levels and start their journey up. Plus there are several professional-quality mods developed for years (even decades at this point) by its vibrant modding community, which basically give you free games for free (a favourite of mine is the fantasy total conversion Fall from Heaven II).
If you want to try a more modern game,
Old World, designed by Soren Johnson (lead designer of Civ IV) also shines for its design. It adds some storytelling elements (events and characters), which are toggable. The developers are still adding new content and are committed to updating it on GOG.
Among the classics of the 90s,
Master of Magic is very fun to play and easy to pick up. When I played it for the first time not so long ago, I was pleasantly surprised at how well the gameplay holds up in this modern age. I haven't played the modern remake yet.
Amen to Civ IV. The first and second and third are lovely as well, although one would have to tinker a little bit to the screen resolution right on III, and the first and second might have to be hunted for (not in GOG).
I am thrilled by Old World. I hear that there are Civ designers involved there.
There is a remaster of Master of Magic, although it seems to hung a little in my machine (YMMV).
Fonzer: I like eador genesis or eador masters of the broken world with fixers mod for the second similar game. The second game at least has a proper save system but the games don't go on discount anymore.
The campaign is very hard and repetitive. I am not far with motbw but i am was far with eador genesis.
Think the game is a little inspired by heroes of might and magic, but the heroes can fight in the battle. To me it's a very interesting 4x game
Good games, but a bit unforgiving for the newcomer.
vv221: Alpha Centauri is the very best 4X that ever was, so I strongly suggest giving it a try if you are not frightened by the dated interface. Surprisingly, its biggest strength is its top notch writing. No other game ever came close to it on this front.
Palestine: With a
sonorous voice, I echo the quoted sentiments of
vv221.
Sid Meier's
Alpha Centauri possesses an unparalleled otherworldliness quality that draws the player inward. It is profoundly satisfying, and, in my opinion, it intrigues the mind in a manner that the standard, history-focused Civilization series (even if obviously related) can not compete with.
Since you have professed inexperience in this genre, it
might be preferable for you to
view gameplay videos of Alpha Centauri, Civilization IV, or others. You may find one that entices.
A very nice game. There is a strong backstory and a plot that unfolds as you play. Very well done. In case you feel curious, the story and design was strongly inspired by Frank Herbert's novel
The Jesus Incident.