Okay Bali: I personally avoid Kuta/Seminyak unless you're really looking to party. The sand is grey and the beach is featureless, even though everyone goes there. Maybe to check out for a day, but much more striking scenery and beaches are in the south, the Bukit Peninsula. More relaxed, chill vibes. Think surfers instead of large men in speedos :) Specific beaches in Bukit: Uluwatu has striking cliffs (also a monkey temple and traditional sunset dance to check out), Padang Padang is a nice spot, Balangan is one of my favorite beaches, very chill. Rent a scooter and explore!
Ubud, up in the hills is nice too, just don't expect solitude, it's very busy these day, but worth a visit.
Hm, this is making me want to go back to Indo! I hope you enjoy it!!! :)