In terms of flexibility and overall smart design, I'd probably go with Space Empires IV. It's pretty reasonable in terms of what you can offer or demand (resources, technologies, starships, control of colonies, non-aggression, contact information of others, maps, war against others, et al) without gratuituous and gamey silliness like unbreakable timeouts for non-aggression pacts or massive inexplicable bonuses. I think that the ability to interfere with inter-empire messages via espionage was a nice touch (one can even forge declarations of war, heh -- now that was a bit too powerful). Non-interference was a useful state; it was a mutual statement of intent that you wouldn't trespass into each other's areas, but you could and would still freely shoot each other if you did meet.
It really was meant for humans, however, and is more than the AI can truly handle.
In terms of coherence, I'd go with King of Dragon Pass. Clans did take into account how you were behaving (generosity when they were having trouble helped relations; raiding them and seizing their people as thralls, on the other hand...), weak clans didn't really make arbitrarily stupid demands of massive tribute like is common for Sid Meier-associated AIs, some level of mutual irritation was common (small-scale cattle raids, for instance) but random feuds weren't common, nor were massive anti-human conspiracies. But KoDP is a special case, because you're playing a story, really.
