hi avi,
i can give you suggestions if you want to know more about Bali (currently in my top 5 of favorite places in the world)..
from KL to bali i would suggest to fly air asia.. and if you want you can even stop by at Jakarta first.. from Bali to Lombok you can take a ferry..
things to do in Bali:
1. see the traditional dances: Kecak, Barong, etc
2. if you love beaches you have to go to these places:
-Kuta:very touristy and now is a bit dirty, but still, you have to see what they got to offer,
-Seminyak: nice beaches with posh places to sip cocktails,
-Dreamland: ultimate surf beach,
-Nusa Dua: nice beaches, with expensive hotels.. just go into any of the hotels here.. buy something from the restaurant & enjoy the scenery
3. Ultimate hangout spot: sunset at KuDeTa.. my favorite place in Bali.. crowded with hip people, really nice place & good peach bellinis
4. go to Ubud if you want to see a traditional very artsy Bali village.. where the resident painters & artists live..
well, basically I go to Bali to sleep in the beach, catch up on some reading, eat good food & party at kudeta...

but if you wanna do hardcore touristy stuffs, you can also ask me if you need some advice..