Really depends on budget. If you are on a tight budget, look around Kuta/Legian. These two "suburbs" are basically "typical tourist Bali". Markets, bars, clubs and beach. If you can spend a bit more id suggest looking into Tuban. Slightly more expensive than Kuta or Legian, but most hotels come with private beaches. 20 min walk max (without stopping) from Tuban to Kuta beach. If you're after luxury resorts take a look at Nusa Dua, Seminyak or Sanur. Nusa Dua is about a 40 min drive from Kuta, but if you're staying in Nusa Dua you can afford the cab fare
The other two are close and cheaper than Nusa Dua, but still more expensive than Kuta/Legian/Tuban.
One hotel I have frequented in the past is the Ramayana. It is right on the edge of Tuban and Kuta. 5 min walk from the beach, right near the "art market" (doesnt sell art, don't know why it's called that). It's also far enough away from the bars/clubs that it's not a problem, but close enough if you do want to walk there.
If you have any other questions just ask. I've been there 6 times now so hopefully I can help you a bit. Also, being an Aussie forum, I'm sure I'm not the only one who has been to Bali a few times