We are also still deciding whether to sail from Sicily, North, toward the island of Stromboli, or South, toward Malta.
There are numerous islands between those destinations, for us to stop at.
So, we were also wondering which of those islands would provide the "old world charm" along with historical sights, great food, etc., and fit into a prevailing wind pattern to visit by sailboat?
Any suggestions / advisements would be greatly appreciated!
I never been in Malta but I have heard it is great, specially out of Summer.
In Sicily I have been several times even if my knowledge is limited since I only know the Coast from Siracusa to Milazzo (a little bit more) but I was not very impressed. In all those miles you can only find three good anchorages: Siracusa, Taormina and Marinello (Oliveri). Siracusa and Taormina are great towns (you have to take a bus to Taormina) and Oliveri is just a small town were you can eat well by the beach in a very nice setting.
Regarding the Islands to the North (Eolien Islands) those I know well. Stromboli is to deep to anchor, they just offer you a lousy buoy for 35 euros (lot's of sea motion and not a decent shelter. You cannot stay there if the weather gets worse).
Vulcano has two nice anchorages and with nearby Lipari (one anchorage) you will get complete protection. The Islands are nice but nothing special. On Salina you will only stay in anchor in very settled weather. There is a Marina (about 70 euros).
I would say that if you want to sail in Italy Sardinia (and French Corsica) are much nicer, including the historical towns, I mean they are not big but they have that kind of charm that I think you are talking about. Elba is also very nice and very unjustifiably unknown. Ponza is also very nice, even if small, with lot's of good anchorages.
I hope it helps.