I went to Bali last November and stayed at the IC Bali,

I would instantly go back there as the hotel and service was excellent but my wife wants to try somewhere new.

I also stayed last year at the Marriott Goa for a week, I thought this was an excellent hotel with good facilities, It is in Pananji, Panjim therefore is close to most lively places. I am Marriott Gold and therefore would get Exec lounge access and an upgrade, this is still not as good as The Upgardes and Benefits i get at Most IC's however if the iC Goa is that Bad then it males sense to go somewhere else.

Phuket is def an option, my brother is staying at the Holiday Inn Phuket and has said its a good hotel, I really did wnat the RA treatment but I guess you cant have everything.