Just to clarify, if you already have sent a delegation, the embassy will not further increase the diplomatic visibility, so unless I want to reveal the enemy capital I usually don't bother spending that 50 gold for an embassy. When you are going for a religious victory it makes sense not to accept delegation and embassies from civs that have founded a religion and you still have to convert. In all other games I gladly accept that free gold.
Both your first spy and the ability to establish an embassy become available once you research diplomatic service (spy at castles only for Catherine). If you build the intelligence agency you can get your first spy earlier.