I will highlight a few ways in which Master of Magic is complex, but in a good way. I don't claim that these have never been used again since, but I rarely see them well done. An obvious point of comparison will be Civilization IV, as the de facto gold standard of modern 4X titles. Pre-game choices / replayability
You MMO kids probably think of character customization as choosing how your avatar will look. More veteran role-players will know games in which you have to spend fifteen minutes picking stats for your character before you can even start playing, as opposed to most modern-day RPGs that just let you pick a class and maybe a race and roll from there. Strategy games rarely give you much choice in that regard. Recent ones usually let you pick from two to five factions and that's it for customization.
In Master of Magic you can pick from 14 pre-made wizards and have the option to design one yourself instead. Gameplay actually varies quite drastically depending on these choices. Via allocation of 11 so called picks, the player can customize what kind of spells he will be able to wield, how powerful these will be, and what additional traits his wizard will have. If you choose to be a famous warlord, for example, you will only have access to eight spell books, limiting the amount of spells you can access. Overall the player has the choice between five types of magic and 18 different traits plus the ability to allocate various amounts of picks into each type of magic. Once a wizard is chosen, the player can also pick between 14 different races, making the amount of meaningful combinations so high that I don't even dare to calculate it. Compare that to Civilisation IV in which you get to choose a civilisation and a leader. These choices result in you having two of 11 traits, a special unit, and a special building. While these choices are relevant, most games of Civilisation IV will look similar no matter which choices you made. A Master of Magic game on the other hand can differ drastically from the next. Way back when I first got Master of Magic, I had no access to the internet and my only source of information was the (gigantic!) strategy guide. I spent hours and days browsing through the tables in there to find new powerful starting strategies. Obviously, you don't want a game that requires a humongous strategy guide to be playable. Master of Magic did that right. You could just pick a pre-made wizard and play a game, but if you wanted to you could way deeper.
Specialized unitsRemember me complaining about the lack of interesting items in World of Warcraft? That game is not alone. Civilisation IV units mainly have one (!) stat that is relevant for combat, for example. Sure they can have some extra abilities like a bonus against mounted units or the ability to fly, but generally a unit's power is what matters.
In Master of Magic, units have four basic stats - swords, shields, hearts, and the number of individuals in the unit. The manual lists an additional 69 special abilities (some of which are a bit redundant.) Units can also gain experience and be enchanted by positive and negative spells. This leads to very interesting battles in which you have to weigh the contnets of your army against those of the enemy. Your super powerful hero may tear up dragons without problems, but fighting the cheap, armor-ignoring phantom warriors he might be toast within seconds. Maybe you have a true sight spell to help him negate those phantom attacks?
The number of individuals in your units also matters highly. A spell that gives +1 sword will do eactly that if you cast it on a single individual. If you cast it on a unit with 6 individuals in it, you will gain +1 sword for each one of those.
Items are similarly complex: Not only can they improve your hero's stats, they can also contain pretty much every unit enhancing spell there is in the game, as well as some special effects. What's better, you can create these items yourself, given enough expenditure of mana.
Dungeon crawlingIn many 4X games, such as the Civilization series, you are either at war with enemy factions or you spend your time peacefully growing your empire. In Master of Magic on the other hand, your armies always have things to do. The world is rich with dungeons, mana nodes, lairs, and wizard towers guarded by a variety of creatures. Your heroes can lead expedition teams into those to gather experience, items, gold, mana, and sometimes even a prisoner. If your army is powerful enough, it can even use a wizard's tower to switch into another plane of existence - a whole new world to explore and conquer. Except for maybe the very start, you should always have something to do in the game.
What it all means
I could list more great features here, but this post is already too long. Maybe I'll come back to this another day. What I mean to point out is, that high complexity in a game can drastically increase both its interest to me and its replay value. I know not everybody does, but I quite like figuring out new strategies for games, even with spreadsheets if need be. Master of Magic shows that you can make a game that's incredibly complex, yet doesn't require an EVE-like learning curve. If you've ever played a 4X game, you can start into MoM right away - but you can stay there for ages.
Obviously the game isn't flawless. Aside from the age-related issues, empire management can become a huge drag in the later turns of the game and there are various bugs that can kill your fun. None of these touch my original point, however, Civilisation IV has shown that those issues can be overcome. The main issue that I have with complexity is the difficulty of balancing the game. If you've ever played with life-magic-empowered halfling slingers in MoM you will know what I mean. There is simply such a huge amount of combinations in the game that balancing them all will be extremely difficult if not impossible. The common solution here is to make a less complex game - but is a bit of imbalance really a big problem?
In mult iplayer, balance is a big issue. While I would love to see a highly complex, balanced, multi player game I don't think it's really possible. For single player games though, I have no quarrels with some imbalance here and there if it means I get to actually think about how I'm playing.
