When you get accustomed with the 4x genre, don't miss Alpha Centauri.

What is it with people thinking HoMM and Age of Wonders are 4X games? They're not. At all.

Wikipedia would like to have a word with you...

https://en.wikipedia.org/wiki/List_of_4X_video_games

Indeed, it is. That said I'm not sure I would recommend it as "baby's first 4X." Granted, those right-click tool tips can be invaluable - hell, when I first started playing way back when I hardly ever had to look at the thick manual since most everything I needed to know was already provided in-game; now that's what I call great game-design ;) - as it may be a bit overwhelming for a complete newcomer.

I'd actually recommend the original MoO over the sequel. It's quite a bit simpler while generally providing the same mechanics. It's also still a good game to play, even though its look and interface have not aged nearly as well as MoO 2's. *shrug*

Either way, that double-pack is still some great value.
Wikipedia is great and all for a general reference, but it's not exactly what I would call the be-all answer to everything.

I actually fired this up the other day.

It has not aged well.

I would not recommend it anymore as a starting place, despite how many hours I plowed into it 25+ years ago. :)

I had to google 4X on google just to undertand the implication of one of the most frustrating yet fun games I have played.

I would recommend the DS port of Civilization, but expect the AI and somewhat of the RNG aspect to kick your ass back where you were born, Gandhi and Napoleon are merciless, I tell you.

If it hasn't aged well it must have been like the best game ever made 25 years ago. I only played it first time a few years ago, and loved it. Compared to Civ 1 and 2 the AI puts up a much better fight even when you have mastered the game, and each game you play is different (due to the randomness of which techs are available), while every game of Civ 2 follows the same pattern.

Ahem :)

Master of Orion 2

Beware: Might and Magic is NOT the same as Heroes of Might and Magic. M&M is more RPG, while HoMM is strategy (and I wouldn't define it as 4x). Both are good, and both have a lot of relations, but don't get the two series mixed up.

Master of Magic is one of my favorite 4x, and it has a lot of replayability. It has been so long since I've learned how to play, that I'm no longer sure how easy it will be to learn from scratch; I want to say pretty easy, but I'm not sure. I can personally attest that several helpful people watch that sub-forum, if you have questions.

Alpha Centauri. It's relative easy to get into, and has a lot of strategic depth so you can play it for a long time.