Seven Kingdoms 2 - The Fryhtan Wars, often less than ten dollars. Try amazon.
Came out in 1999 and it's still great fun to play. Works on XP. Don't know about the newer operating system. War, trade, economy, spying, troops that learn and can defect, villagers that can rebel, spies that can assassinate, take over forts full of enemies, gods that can bestow gifts or attack, racial harmony.
It's a bit like Age of Empires. You have the Romans, Persians, Greeks, Chinese and some others. Then you have the Fryhtans, who are monsterous creatures that start off very strong and get stronger the more people they kill. There are resources to mine and factories that employ townspeople to make goods, but each person in the game has numbers for loyalty, combat ability, hit points, leadership and some have spy abilities. If your troop's loyalty falls below thirty, you run the risk of them defecting to other kingdoms. This can happen to generals too. You can adjust the loyalty of everyone by giving honors which cost money or you can keep them in your fort under the guidance of a good general of the same nationality. Your kingdom has a reputation number too. It can go up or down. It can plummet dramatically for a number of reasons, perhaps the most crucial being you've attacked civilians of your own nationality or someone you're at war with. When your reputation drops, it gets harder to bribe other generals and loyalty throughout the kingdom goes down. The most common problem with low loyalty is rebellions. Peasants will leave teh town and start attacking it or other buildings. This can start a chain reaction. It's very difficult to control a rebellion. Killing rebels counts as killing civilians and that makes your reputation go down which lowers loyalty throughout the kingdom causing even more rebellions.
Losing your king in battle causes a drop in reputation. Losing an important fighter also causes a drop in reputation. If your towns are taxed to the point where they are not very loyal, the loss of a king or important fighter can trigger rebellion which can spread like wildfire. Lack of work will lower loyalty. Full employment will increase loyalty and so taxes. With more money you can hire skilled fighters and heroes. In the beginning of the game you'll try to convert independent towns to your kingdom so that you'll have a larger tax base and a base to recruit troops from. They have a resistance number which goes down if you connect a fort to the town and put in a general or king, especially if the general or king is of the same nationality. At that point you can tax them or recruit from their ranks for your army. If you don't have a general of the same nationality, you can still bring the independent town on to your side by giving them grants of money or by giving them jobs in a science tower where they'll do research for you. Or you can put them to work in a factory or war factory, but that last one might get you on the dangerous kingdom list of the fryhtans and they'll attack.
Then there's spying. You can hire them at inns or build an espionage college where you train your own citizens to spy. Spies can change themselves to appear as other nationalities. They can go into enemy forts and towns and show you the troops inside. With research and good spy skills, your spies can steal information about other kingdoms, steal technology, assassinate generals, counter spy in your own villages and forts (expose enemy spies), bribe and steal forts full of troops, create incidents between other kingdoms that turn them against each other while you remain neutral... and a few other things.
There's also diplomacy. You can form trade agreements with other kingdoms or reject proposals. You can ask for aid or military assisstance or a cease fire. You can form alliances or break them (breaking them is bad for the reputation). You can trade technology. You get the picture; there's a lot to think about.
You can improve your reputation by killing independent fryhtans or fryhtans from kingdoms. You can avoid breaking treaties or killing civilians. If you start losing money, your buildings will fall apart and if work places fall down, you'll lose loyalty of your subjects and they won't pay as much in tax. You can also hire townspeople to pray to gods and the gods have many different abilities and benefits as well as a general benefit. Some are destructive like earthquakes and some are beneficial like improving the leadership of targeted generals.
It's a huge headache when you start playing, but it's all very well thought out, an incredible game that makes AOE and most every other RTS look shallow. Single player games can easily last ten hours real time, much of it on pause, trying to figure out what to do or just catching your breath. One negative - the game won't tell you why things have gone wrong. It might look like a bug, but there's always a reason why all your citizens have turned against you, like if your generals disappear - your forts are probably infested with spies. It can be frustrating, but eventually, you'll see the genius of Trevor Chan if you stick with it.
There is a campaign. I haven't finished it. You get choices during the campaign so that it's different every time you play it. It's not that long, but it's somewhat different. Not the most impressive thing about the game though. I've played games with more gripping stories.
There are some nice guides on the internet, but you'll have to look around.
the 1.20 patch and instructions on how to install...
http://www.the-underdogs.info/tech/techelp_s.html#sevenkingdoms2patchingtover120
The seven kingdoms forum at enlight...
http://59.148.144.50/forums/forumdisplay.php?f=63
I don't know if there's anyplace to play online. The game works well on XP. I've got the 1.20 patch. Some of the tutorials within the game don't work though; I hear it's a problem with service packs.
Video of gameplay at youtube. look up fryhtan wars. Kind of confusing to watch. The graphics are similar to AOE/AOK, but probably a little worse. The gameplay excels!