For Bali:
I'd recommend Aquapro Bali, based in Sanur area. I've been living in Indonesia for more than 4 years now, and done more than 15 diving trips to Bali with different operators during that time. I'd say Aquapro is the most professional outfit, with good gears for rental and great divemasters (Pras, Sabre and Ena) all of whom know the sites around Bali very well. Tulamben (Northeast of Bali) has the great Liberty wreck, and I'd recommend a stay at the Mimpi Resort. Amed, about 30 minutes drive from Tulamben has some great, rarely dived sites. Candi Dasa has sharks and some currents. Menjangan Island to the Northwest has nice walls and you can take a day trip in the national park. Nusa Penida, to the southeast of the island and near the tourist areas of Kuta/Sanur/Nusa Dua/Seminyak, has great current rides, the sunfish, etc.
You could do a spot in Bali and stay a few days and wouldn't be disappointed, and the island has plenty of other offerings. Or you could do a safari, and over a week hit all the different dive areas for a day or two each and get a varied experience. Aquapro Bali office is: +62 (361) 270791 and they can also arrange your hotels at very competitive prices in addition to the diving. If you're going for the mola/sunfish, do Nusa Penida in August, and bring at least a 5mil suit, as the temperature drops to about 18 celsius or lower.
Bunaken in North Sulawesi is great, too, but whereas Bali has other, non-diving attractions, Bunaken is basically diving. I'd back up recommendations for Froggies, having stayed there twice for a week at a time during the past two years.
I've recently started going to Central Sulawesi, though, and found the diving also quite nice. There's an outfit in Tanjung Karang, on the west side of the Sulawesi island and an hour away from the provincial capital of Palu. Prince John Resort +62 (457)71710 or +62 811455147 is run by a German couple and has great bungalows overlooking the house reef (spanish dancers, twinspot lionfish, croccodile fish, great variety of nudibranchs, etc). My most recent trip there was last week (May 19-28) and visibility was only 10-15 metres, but water condition started improving towards the end of the trip and I had a great 35m+ vis at one shark-filled underwater mound (Pasi Pome).