Yea expect cool and damp (though not necessarily rainy). What about Malta, Cypress, Corisica? Malta is amazing dude, really, you could spend a very long time there and not see everything.
Anyhow, the time of year you will be going will make thing MUCH cheaper. Also, check into ferries from one country to another - there are several. I know you can go from Malta to Sicily to Italy main land.