great recommendations from ggunn!!!! ditto all.
also, rent a jeep and spend the day driving around the island, stop at Coconuts on the Carribean side, beautiful hill top view, good food and great margaritas, (be careful they are VERY strong!!!!!!!!!!). ask to see the "family albums"
for an on island Mayan experience go to San Gervaiso, on the north side. It's not as impressive as going to Chichen-Itza, but not much is, belive me, but it is a good sized late period archeological site.
the lighthouse at Punta Sur at the south end is also a nice stop.
Playa Corona just up the street form F.A. and Rock-n-Java would be my food additions to the list.
have a great trip, hope it's first of many for you.