An Embassy is used to join an alliance. After a player joins an alliance there is no real benefit to upgrading the embassy except for the extra population and taxes that higher level embassies produce.
Embassies need agate gems for level 10, 15, and 20 upgrades. Players who are friends can gift these to each other. Agate can also be purchased at the game store.