Unfortunately some aanwar's suggested locations are very much ON the beaten path. Locations in and around Kuta / Seminyak / Denpasar are horribly over-touristy and you'll get no peace to take photos as 'vendors' try to get you to buy copy watches and sunglasses. I'm sorry to say even the delightful Ubud has been infected, though thankfully not as much (yet) and is still beautiful. As a general rule, the further north you go the less touristy it is and the more chance you'll get to see the 'real' Bali - truly a beautiful island.
The Tanah Lot sea temple is the temple everyone goes to see, but make time to go to the 1000 year old Tampak Siring, built around a sacred spring. Beautiful rice vistas on the journey too, and only a few miles N-N-E of Ubud. Perhaps take a look at Kintamani / Mount (actually volcano) Batu.
Near to Batu, Trunyan is an ancient Balinese village inhabited by people who call themselves "Bali Aga" or old Bali - reputedly the 'original' Balinese. Their way of life pre-dates Hinduism and is very different from other Balinese. The temple in Trunyan stands under a huge, ancient banyan tree, where the Bali Aga place their corpses instead of cremating them. Visitors are not allowed in the temple, and you can only get to the actual Trunyan village by boat across the lake.
Tulamben is a beach-entry dive which can be made tricky by a big pebble beach and surf, but pretty good once you get below 10m. I've seen Mola Mola at Nusa Penida recently, and a thresher shark at Biaha near Candidasa. Menjangan Island offers some very clear waters and easy diving.
Here's a lateral suggestion - take a cheap internal flight from Bali to Lombok (flight time less than 30 mins) for a couple of days and get a taste of what Bali used to be like 30+ years ago. Lombok is far less trodden and far less populated with stunning unspoilt beaches, primeval forests and rural rice fields where it is still normal to see oxen being used to plough the fields. It doesn't have the 'facilities' of Bali nor it's rich Hindu heritage, but pick up a Kijang driver at Mataram airport and hire him for the day for about US$30-40, and he'll be able to take you to some wonderful places. If you have a lot of time, take a trek up Rinjani, it's absolutely stunning.
Go even further afield and visit Gili Trawangan off the west coast of Lombok, and let me know how my villas are getting along!
Peter