Can't really tell for sure unless you mention what kind of destination you are looking for: mountains, beaches, underwater activities, cultural, nightlife, etc

Well the basic trails of East Java would be:
start on Banyuwangi (Baluran nat park, Green bay, Mt. Ijen) and end on Malang (Mt. Bromo).

Best to enter Mt. Bromo from Probolinggo, though.

As for Bali personally I like Menjangan Island (underwater) and Kintamani highlands (Mt. Batur)