I have not been to all those, but I wholehartedly agree with Palermo and Siracusa. Both are wonderful places to stay.
May I suggest the northwest coast, near the Zingaro reserve as another place to consider? This was a lovely natural area, plenty of beaches to hike to. It was not untouristed, but it was undeveloped - no beach chairs, snack stands, etc - just beaches that you have to hike to. The ones closest to the park entry are busier, as you walk in along the coast they get more quiet. We stayed near Scopello, which was a nice very small town.
Also, I did not get to the Aeolian islands but would love to. If I had 9 weeks it would be high up my list.
While in Taormina, I highly recommend a trip to Mt. Etna. You can drive to one of the base areas and get a cable car up the mountain. It's fascinating. While in Trapani, I highly recommend going up to Erice - by car, bus, or cable car. Get there early and it is almost deserted, very quiet.
I would not have the car in Palermo. I would suggest arriving into Palermo, visiting for several days, then picking up the car and heading on your way. Or ending in Palermo - drop off the car, go into the city, stay for several days, fly home. If Palermo needs to be in the middle of the trip, park the car and leave it in the garage for the entire stay in that city. Palermo is not an easy place to drive, or day trip from. You can easily get a bus or cab to Monreale, everything else is better seen from one of your other stops. Cefalu can be done as a day trip by train from Palermo, if you decide not to stay overnight there.