Quite a few uses of diplomacy come to mind.
- Allowing free passage through an area. Perhaps only along a path, 'tho, or in specified provinces?
- Requests for assistance. GalCiv's one of the only PC games that I know of in which an AI ally will ask for help when it's in trouble (in contrast to demanding tribute).
- Demands for tribute.

Has to be handled carefully; nations which give tribute should not provoke war, and should be entitled to live without further provocation in turn.
- Sharing of map. Partial or whole, hm? The ability to lie here could be amusing, too.
- Sharing of scouting reports, e.g. current estimates of enemy army sizes. "Our scouts report that... Caelum scouts report that..." et al in the province information. Perhaps should have a "we're lying; exaggerate/minimize by this much" slider.
- Gem trading/item trading. An item/gem exchange might be pushing it, 'tho. ("Fire gems up 0.05 to 1.85 Astral, Caulrons of Broth down to 30 Astral, et al"). Heh.
An ongoing gem-trading treaty could help, e.g. every turn A sends a certain set of gems to B in exchange for a similar allotment.
- Perhaps agreements on future targets? e.g. if two nations could both soon conquer a number of independent provinces between them, deciding who takes who to eliminate the chance of accidentally starting a war. This could be supplemented or enforced by a non-aggression pact which would cause mutual withdrawal rather than a battle if they do both attack the same.
Could also be stated as "sphere of influence".
A lot of this might be fairly hard to do, without resorting to the usual "AIs gang up on Humans/main threat" deal. Some of the mechanics would still be helpful for MP, e.g. not having to manually type out army estimates on a shared foe.