Something that has not been mentioned that I've seen: The Waterborn by Greg Keyes. A great fantasy book that also has something of dominionsesque flavor. I've even thought about making a map/mod based on it, might look something like a small map duel between Pangaea with a lord of the wild and T'ien Ch'i with an oracle.
There is also a sequal to it called Blackgod that is about as good.