We had no trouble doing it without a GPS. Also, though Palermo was a nightmare, Catania wasn't bad at all. I agree, though, that the southern coast is terrific.

There are some great papermaps (yes paper!) of Sicily you can buy and you can survive without a GPS. If you are driving in towns looking for certain specific locations GPS can be helpful. If you just need major areas or roads the papermaps and signs will be fine. Like much of Europe you need to know the town you are going to and the ones just before and just after as not every road junction lists everytown so you need a basic knowledge of the area you want to go if it is small. Bigger cities will not be a problem they are always labled.

Catania to Palermo without a car normally means bus and they are fairly cheap. The train means you have to go to Messina first so unless you want to view the "scenery" take the bus if you do not rent.
(There is no standard commercial flight between CTA and PMO)

If you do rent and are in it just for speed take the main highway but if you want to explore the south coast is nice, though the drive will take you a long time relative to what many from North America and some parts of Europe think of when considering distance and time.

This time of year is pretty slow. Your best bets during winter are the big cities, Taormina, Nicolosi and the archeological sites (Agrigento and Siracusa). I previously lived outside Catania, but found Palermo to be a little nicer city; though Catania has improved much the past few years.

Last summer when I was there we stayed a couple days at the Sheraton in Aci Castello right outside Catania which was nice during the summer time and dirt cheap points wise (3k a night). Aci Castello has some good restaurants in the area.

we have been all over the island and it is a fantastic location

assuming that you go in spring I don't think that beach days are in the cards. that being said, I would spend a few days in Palermo - it really is a fascinating city.

rent a car - it is the only way to get around, I would second the GPS idea. you can buy a chip here in the US to fit into yours if you have a unit

stop here for a selection of ceramics at good prices
http://en.wikipedia.org/wiki/Santo_Stefano_di_Camastra

head south to this. it is a must visit
http://en.wikipedia.org/wiki/Villa_Romana_del_Casale

here for spectacular greek ruins
http://en.wikipedia.org/wiki/Agrigento
eat here with a fantastic view of the temples. very good food
http://www.tripadvisor.com/Restauran...to_Sicily.html

beautiful town rebuilt after the earthquake
http://en.wikipedia.org/wiki/Noto

hillside town
http://en.wikipedia.org/wiki/Ragusa,_Sicily

siracuse is a great town with good food and sights

Catania is nice (somewhat gritty) but I wouldnt spend much time there when there is so much to see and do elsewhere. Palermo is a better choice for a big city. I would fly out of Catania though

the west coast of sicily is nice but more beachy

no charge for drop off fee with most rentals(we had hertz) . so one can pick up in catania and drop off in palermo (or vice versa).

I've been to Taormina and it was wonderful. Very friendly people.

If you or your wife are fond of mysteries, you might want to get in the mood for Siciliy by reading some of the Inspector Montalbano books by Andrea Camilleri. These books have made me want to go back. Gives you a good flavor of Siciliy, as does Anthony Bordain's visit there for the show Parts Unknown. You can find these on YouTube. Not the No Reservations show.

Taormina is very nice.

We took the Godfather tour there and it was wonderful.

Really wish to go to Syracuse and Palermo.

We loved Taormina.
From my trip report last year.

Great suggestions so far. Would agree that the southern coast is a beautiful drive and if you do it you could spend a day or two in Trapani on the west coast, a beautiful seaside town. A half-day side trip from there would be to take the funicular at the edge of Trapani up to the mountaintop town of Erice. Have to admit I was a bit scared in the cable car since you're going straight up - 750 meters in 10 minutes - but it was worth it for the views and walking around town.

On the way to Palermo - or as a side trip from Palermo - you could visit the temples at Segesta. Another side trip from Palermo would be to visit Cefalu, further east on the coast from Palermo, a beautiful little beach town on the end of a point.

Looks amazing thanks!!!!

We were in Sicily two Januarys ago. Our first day on the island involved catching a late mid-morning ferry over to Medina which allowed us to make it to Taormina for lunch. Had plenty of time to see everything we wanted to and enjoy dinner, but could have stayed another day in that area. Taormina was breathtaking.

Stayed at the Sheraton Catania. Worked well for us. Next day did a day trip to Siracusa, which was also a day well spent. It was off season so many places (including museums) were closed, but still found plenty to do.

We had a 3rd day based in Catania and had ideas on another day trip - possibly to Piazza Armerina or Ragusa, but it was raining and my son and wife were sick, so we stayed close to the hotel. Did drive around Catania a bit.

From Catania we drove to Palermo with a stop in Cefalu. The town was empty, but it was another stormy day and the ocean had huge waves - allowing us the most amazing lunch right on the rocks with water crashing against the restaurant. Cefalu is definitely worth a visit if time allows.

From there drove into Palermo and stayed at the Hilton. Great location and stay. Enjoyed a couple days exploring Palermo.

In addition to what others have said to do in or from Palermo, will add that we spent a Sunday out in Castellammare del Golfo and enjoyed it. It was really cool with the picturesque beach yet snow capped mountains in the distance. There was a weekend market along the beach walk and we enjoyed a great late lunch at one of the seafood places as our last meal in Sicily/Italy.