Thanks for all the suggestions, Swisstrav, Azotomix & Lawrence! Im getting really excited about getting there!
Yes, I do decide last minute where exactly I will go on vacation. Im airline staff and want to fly stand-by.
Sicilia is a place I would like to go though. Im going with a friend who does not dive so Im not sure if Malta or a place near the red sea is really an option. For non-divers it might be kind of boring.
Anyhow, it sounds like the small islands are worth checking out, will read some more on that! Thanks for the websites. That is very helpful! At least I now know where to start looking for more info!
Wish you all lots of diving fun too!