Dominions 5: Warriors of the Faith

I haven’t pulled the trigger on 5 yet but 4 was worth it to me even if I had never played multiplayer. The AI is good enough to keep you on your toes while learning the game and to exploit any huge weaknesses in your play. At the same time it is weak enough that you can play more casually and have fun messing around with the huge number of non-optimized choices available.