Strait of Gibraltar seems to be flooding with battleships. The straight is a nice place to wait for them, though tad risky.
Valletta is a crappy place to visit, so I think you should head for Port Said and Alexandria. I think the Med's fun, but not very spacy.