Well, what you do is really personal taste but I will give you my ideas. For Palermo, you can walk from the ship into the center of town or use public transit. Google as place called tha Capuchin Catacombs. The place is quite amazing and macabre. Its on the far side of town from the port, but you can use the local buses to get there (just ask the tourist folks when you get off the ship) or take a taxi.
As to Civitavecchia, there is a free port shuttle that takes you from ship to the port entrance. From there, its a 4 block walk (towards your right along the water) to the local train station where you can catch the train to Rome. In Rome, you are on your own and there is a ton of info on-line and in books to help you plan your day.
Ajaccio is a place where you can walk from tender pier into the small town. There is a nice sandy beach off to your right (as you walk up to town) where you can spend a nice beach day. Cafes and restaurants nearby will take care of your lunch. If you are interested in geology and seeing the island, take a tour (if offered) to the Calanches (interesting rock formations).
Alghero - you can explore the old town on foot. Its also a good place for water-based activities.
Mahon - A very interesting place that my wife and I would love to re-visit. When Franco ruled Spain, he gave lots of money to the sister island of Majorca, but hated Menorca (gave them nothing) because they were politically opposed to his administration. As a result, Majorca is overdeveloped and Menorca is still relatively unspoiled (but its now being developed). Personally, we prefer to rent a car in Mahon and drive around the island. There are some gorgeous remote beaches which can be fun (to get to one we had to literally drive across a cow pasture and close the gates behind us) and with a car you can see the entire island.
Many thanks, very helpfull, Hank
Can you tell me if there are 'departure' signs, especially in Rome, which tell you which train/time/platform etc.,
Also, does a return ticket cover any return train?
Great questions! There is a large overhead board in Rome (they may have finally made it electronic) that shows all the departures. The board lists multiple destinations for each train, the track, and the time. The trains to Civitavecchia all go beyond that stop, so you need to look carefully at the board since the destination will be one of many. If you have a problem finding the right train you can simply stop at the information desk (they speak enough English and are used to cruise passengers asking for Civitavecchia). The normal ticket will cover any of the regular local trains, but there would be a supplement if you take one of the special high speed trains (like ES, ICE etc). If you accidently got on a train where there was a supplement, the conductor would collect the money. Most of those high speed trains require reservations, so you would normally stick to the locals. There is always at least one per hour and often several more. I suggest that once you reach Rome, carefully check the schedule so you know your return options before you ever leave the station. Mske sure to give yourself a minimum of an hour extra just in case the trains are running late. And always have a desperate back-up plan. We have never missed a ship (in over a dozen Med cruises) but we always take the name and number of the port agent (listed in the info given on the ship) and have enough money and/or credit cards so that, in the worst case scenario, we could catch-up to the ship the following day. A good idea is to always carry a copy of your main passport page for ID purposes. Hope this helps. Its really not that difficult if you do a little planning (you are doing that now). My only caution would be that Rome is a very large sprawling city with the major sites scattered in a few different areas. Although I generally do not recommend tours, there is much to support taking an all-day tour on one's first visit to Rome. This is especially true if the tour includes a visit to the Vatican (some tours can bypass the long entrance lines). If you do go to Rome on your own, its a good idea to have worked out a plan since the large city can overwhelm the unprepared.