Kasey, when I went to Bali in October I didn't book any accomodation until I got there (apart from my first night - which I ended up postponing for a night after Malaysian Airways lost my camera case for a day), and that worked out fine. It makes travelling a bit more stressful - and means that you can't immediately switch your brain off as soon as you step on the plane - but it is certainly very cost effective. This wouldn't work as easily with a single resort destination like Wakatobi. I don't really recommend it. But certainly possible.
-------------------
Re-Tulamben. Fongwee, I think that the Liberty is an amazing dive site and certainly worth diving at least once with every lens you own! Viz is best there in the morning - so do wide angle then. Other sites are well worth checking out, for specific critters like pygmies or froggies. Non-photographer buddies might get a bit bored with Tulamben if you stayed a week. But photographers never!
To give you an idea. Here is what I did at Tulamben staying Seraya in Oct 2005 for 4 days - and I still wanted more! In fact going back in September to do more! Oh, and diving the Liberty from Seraya by RIB is much better than walking up the beach IMO - i tried both while I was there!
Anyway, I did 4 dives a day. 16 in total. 6 at Liberty (always first dive of the day). 1 at River. 1 at drop off. 1 at Mimpi house reef. 1 at Alamanda. 6 at Seraya house reef. My average dive time was 77 minutes. Pictures:http://www.amustard.com/bali/
As you requested, Frogfish is the expert on Bali and his advice is as good as you'll get.
Alex