How difficult is this game?

[Twan]

Yes there are 5 difficulties from easy to impossible (impossible AIs may be really hard to beat, but mostly because they start with lot of bonuses).

edit : and sector24 is right, there are also a lot of ways to make SP challenging once normal maps become too easy

How does it compare ? Hard to say.

I think the dominions AI isn't as good as the really good ones (ie Civilization or Galciv AIs), but far better than the AIs of Paradox games and most indie wargames.

About complexity I would say a dominion SP game against non impossible AIs (if you just use what you need to win = perhaps 5% of the content) isn't more complex than any of these games, but there are then several more layers of deepness once you play against humans (the only games I see with an as big number of combos are card boardgames like Star Chamber).