travelinmanS and I have obviously approached this question from the same perspective. But I agree with SteveFenton too: Kuta is not the place I would stay for relaxation. And my concept of Nusa Dua is that it's generally too Westernized with megahotels for me. I'd split between the Ubud area (the artistic heart of Bali and within striking distance of a great many cultural and natural sites) and either Legian/Seminyak or Jimbaran. Mr. Megatop and I did that in May this year and thoroughly enjoyed every minute of our stay in Bali.