Looking for a good fantasy strategy game
1.) I'm looking for a turn-based empire-building title -- think Civilization crossed with Lord of the Rings. I do not want an RTS like the Warhammer games, no matter how much fun they may be; that's just not my cup of tea.
2.) Must have an open-ended campaign or "sandbox" mode. With very few exceptions, I've never liked playing campaigns that consist of a series of missions. I like to just build up my race/nation/empire in a more free-form environment.
2a.) A random map generator would be great, but it's not a make-or-break issue. (Obviously I have no problems with the TW games lacking randomly-generated campaign maps, for example.)
3.) Good AI. This is a must-have for me, as I play mostly singleplayer games. Not that I expect computer opponents to be brilliant, obviously, but it would be nice if they could at least give me a halfway-decent challenge.
So given all that, is there a fantasy game out there that fits everything I just listed?