We stayed at Cefalu on the north coast, which was OK and had train connections to Palermo and to the ferry point for the islands.
Palermo is fairly scuzzy in parts and almost what you expect of preconceived ideas of Sicily (southern, poor, Mafiosi-influenced) but still worth a day. Definitely go out to Stromboli on the ferry. Get there in the late afternoon and start the climb up the volcano as the sun is going down. You get fabulous views out over the sea to the mainland and, once the sun has set, you turn a corner and see the glowing stream of lava coming down the hill. You get up to the top about 23.00 to midnight and can spend time up there looking down into the crater (and the lava). The walk down will get you back around 02.00-03.00 before the ferry in the morning. I think you can do it on your own, but probably safer to do it as part of a guided walk as we could see the route we took down from the ferry the next day - scree above some decent drops!
Other than that, hire a car and visit some of the scenery and history - it's a bit like Turkey in that it has plenty of both. We had a Smart and buzzed around the west coast (Trapani and Marsala) as well as a fair bit of the interior (Corleone, obviously) and some of the nature reserves. We missed out the east coast (Taormina, Catania, Syracuse) but would definitely go back again. Food and wine is also excellent.