Why the heck is Gibraltar so important in this question? If you see the map a Medieval state that takes over Tangiers and Ceuta already has a safe route through he Straits. Portugal managed to have a presence on the Mediterranean because of this before the Iberian Union. Geograhically speaking, Tarifa seems actually more threatening...
Certainly any maccaronesian archipelago (Madeira, Açores, Canaries, Cabo Verde...) would be a nice stopping place for a power with interest on the Americas. In the case of the Balearics I don't see the point, unless it is to provide manpower and secure dominance over the Western Mediterranean.
In the case of the "undefendable" Moroccan ports... well they are as defendable as the ones on the other shore I think... or actually more because Morocco allows less population and has been historically less tech advanced and thus less threatening in matter of sieges... Bear in mind that if that Italians occupy ports on the southern coast of Spain they are going to piss off the Spaniards, even if this is before the conclusion of the reconquista, because they see dominion over the Peninsula and restoration of the Visigothic Kingdom as their mission on History. And against the Spaniards, the pretext of taking lands from the infidel doesn't work. If that ports are just on the other coast, there is not only no problem, the Spanish actually could assist in its defence against any Moroccan try to take them back. Why everyone assume the relation between the two peninsulas must be bad? Castile and Genoa were very good buddies in OTL, and when Spain unified it not only continued, but erased the former Aragonese/Genoese rivalry...
Florence on stereoids would be an option. Maybe I'm too much influenced by Max's Chaos TL but I think Florence was actually on the way of taking over the Italian Peninsula before the Black Plague. It even managed to invade Corsica and Tunisia at some point, retaining positions there for some years.
Problem is that the Serenissima is too much East-oriented, and with some historic tendency to annoy everyone around her...