Since you are considering things like "The Great Tower", I will make suggestions heavily utilizing magic in the construction.
First you want to find someplace that already has a Magic Aura as your base if possible, since this will make life easier in the long run. A small island, to tiny for normal use, would be perfect as the Aura anchor. This also ensures you are not trying to build your island in extremely deep water (the Med averages 1,500m in depth for example).
Using the level 30 to form the outer wall in a open ended cylinder, modified to create a four sea gates (+1 Mag). Use another version of that spell to create a open ended roughly rectangular prism in the middle around your anchor island. You can make the walls slightly higher and dimple in the walls in line with the sea gates.
If you want a truly epic tower, consider using a solid stone cylinder as the base. If you are willing to use workmen and/or magic to shape it, then a higher level version can create a huge cylinder which since it can get by without the added magnitudes for Complexity. The level 35 will give you 240 paces of height and over 81 paces of diameter.
For back-fill I would recommend clay with two paces of top soil, since this will provide more support than straight dirt, while being waterproof and allowing things like underground cisterns.
If you pick a base location not overly deep (that anchor rock), you will end up with a fortified ring some ~3 miles in diameter, with four sheltered harbors accessible by sea gates, a square island inside the outer wall (even greater in height and connecting to it at its four corners), and a stone cylinder 240 paces high and over 81 paces in diameter. It would have an ablation layer and back fill of clay (with 2 pace topsoil, level 30). That should be more than enough space for your needs.
Might I recommend the Azores for an existing, likely magical island to build your larger island around. I think it’s deeper there than the Mediterranean but there is already an island with plant and some animal life and with little to no previous inhabitants. A bjornaer or other shapechanged magus could likely easily find it by following sea birds while an invading army is unlikely to find it (least until its discovery a couple hundred years later. Anyway, that was my thought when I was thinking of pursuing the island-building idea in another game.
Do you mean to create a floating island, like Delos?
Because then you need to consider how high a tower you want to build, due to the same stability issues as with a ship.
I now want to have a giant ball of pumice with a tower leading down to the seafloor from where someone tried to do this, got their calculations wrong and had the whole thing tip over.
There don’t seem to be a whole lot of lakes large enough in Europe.
EDIT: And it doesn’t seem like the sanctuary idea is all that great if you’re close to the shore of a lake barely wide enough to fit the island. Much more of a sanctuary to be out in the middle of the ocean surviving partially on magical desalinated water.
Of course it's magic, but the question is how. That's like answering "it's science!" when asked how a particular device works- sure, but how. Is there an enchantment holding salt water back, purifying the water as it enters? is the lake elevated and fed by a magical spring? Different methods have different implications and costs.
Since a floating island is in effect a giant ship, this would have much the same effect as a keel does. The more you build up on top of the island, the more important such a structure under it will have. Additionally it will allow some interesting effects if enchanted such as an "air lock" for exploring and collecting things. An Aquam focused Magus could also create a great lab there.
You are aware that pumice only floats until it's air pockets fill with water, the material itself is not naturally buoyant, right? Which also means that as you build on top of it and it is forced further under the water that it will lose buoyancy even faster, as well as needing more to support the weight...
of course this might not be known in Europe since it appears the majority of pumice formed came crashing back into shores being dashed against harder rocks before it was floating very long... though the fact that Romans believed it was hardened sea foam suggests that the larger and more enduring pieces were rare in the Mediterranean.
Thats true of modern knowledge of pumice... Not sure on the mythic properties (and I don't remember Transforming Mythic Europe talking about it). I like the idea of an inverse tower!!
I have been pondering the air pockets and how to keep it floating... I also need to reread the section on floating islands and see if i missed anything.