Some years ago now, 2002 in fact, I visited Bali with a friend.
We stayed a few days in Kuta. Beach, plenty of Australian tourists, and you will be hassled every 5m when you walk down the street: "Yes taxi sir?" "I give you good price"...
Then we stayed a few days in Ubud. There was more peaceful, but still plenty of hassle from touts. We visited the monkey sanctury, and a cultural show / dance. This was also the place where I saw a gardener cut the hotel grass with a pair of scissors!
We then moved on to Candidasa, a small town on the coast. Almost no hassling or touts. We stayed in a small thatched bungalow for about $8 per night for the room - a bargain. From here we visited inland temples, and the beach.
Overall prices were cheap, except Kuta which was more expensive (still much cheaper than Europe though). Don't forget to haggle though, we paid more for an ice cream from a beach vendor than our entire 3 course meal with drinks that lunchtime!
We travelled around on the limited network of tourist busses - I think it was this company:
Apart from Kuta, we arrived in the towns and found accommodation there and then, there was no need to reserve, though it was verging on the off-season, May.
I would go back, but to be honest, I'd avoid Kuta completely and head to a quieter place.
The food was delicious all over!
Hope this helps!