I like the idea however, I would want to designate a route because the computer goes through he star planets or non colonizational planets which might have massive wars in them to get to an ally world, IE  Foriegn Invasion always massive battles in the astriod belts.

Bingo.

How about you use the envoy like a starbase builder and have them deploy into embassies around planets? Change the Envoy so that it boosts relations only a little (just enough to get a cease fire when combied with the usual research and bribery). When you don't have to worry about the other faction blowing it up have the envoy deploy into a embassy which would increase relations even futher allowing for some of the more advanced pacts. Give the embassy all the abilities the Envoy had (worth cause, mutual threat, ect...) so that it can still be useful to have around. After it's up the embassy can't leave the gravity well like the Envoys if things get bad meaning they're alot more vunverable. It'd be up the owner of the gravity well to protect the embassy in order to keep the relationship boost high as well as recive the ability bonueses. Also you could potentially add an ability to envoy cruisers that could allow them to sabotage vunerable enemy embassies making them reduce relations instead of raising them allowing you subvert enemy relations getting AI's to fight each other and denying human teammates high level pacts. What do you guys think?  

See I'm not crazy