My main goal for the early game was to find the other civs as fast as possible. In 670 BC I found the Greek&Roman island with one of my suicide galleys (the GL helped A LOT with this, thanks to the 4 moves and safe seas). This was my first suicide galley, so I was really lucky. The Greeks knew Horseback riding, but were otherwise only moderately advanced. I had made a mistake here, playing too much deity, in that I researched Republic at 10% only. It turned out all AI civs always were way behind me in tech.
The galley brought a settler along, so I founded Rusaddir (in 610 bc) on the northernmost of the Greek islands.
It then took until 110 ad before a second suicide galley was succesful. This time I had headed west, and found the Persians&English. I traded their map, literature and all their 300 gold for currency. I never gave away my communications, even though I eventually sold my world map to everyone. I discovered Monotheism the next turn.
In 150 ad I found the American&German&Russian island. They had nothing to trade except for their maps. By this time I had lost 7 galleys (see pic for the red circles). I prepared for a war against egypt by researching Chivalry and building horsemen. I attacked in 320 ad, and finished the Egyptians in 590 ad. I decided to go for a conquest victory.
I built Copernicus in 640 ad and Magellans in 660 ad. Too bad that having both GL and Mag won't give your galleys 5 moves.

After this finding the other civs was easy.
I found the Babs&Zulu&Iroquois in 820 ad and the Chinese&Atzec in 900 ad. By this time I was 2 turns from Military Tradition, and the poor Atzecs&Chinese were still in the Ancient Ages, not having even discovered map making!

Now I had contact with everybody. I didn't particularly search for other islands for some time, so I only found some new guys in 1300 ad. However, this meant I missed one volcano (I think).
The english founded a city on the island to their south in 1280 ad. The first AI overseas contact was made in 1380 ad. It seems they didn't both much to go see the other civs, even though I had sold my maps to everybody. Their slow progress in this field can also partly be explained with anoher factor, which is outside the scope of this thread, however!
EDIT: removed names, fixed typos.