Doh! I knew you could do that in Medieval II at the Bosphorus straights, but not on RTW:EB.

BTW: I've done some research on building ships at Ictus, but I am still running into a major fail.

According to the tech tree on the EB homepage, and the building browser at the city itself, I need a level 4 (Casse Allied Tribe) government and a market #2. I have both of those now (tore down me level 1 goverment), but there is still no option to construct a building capable of recruiting ships.

Methinks I'll go hop on EB right now and march my army north of Yns-Mons.