I quite liked Yogja - the crazy 3D signage is great. We went there after Borobudur in order to climb Mt. Merapi. Unfortunately it was erupting so that never happened.
Borodudur is really great, definitely worth the trip.
Flores is close to perfection for me - still very “off the beaten track” but reasonably easy to get around. We hired a car + driver. The sea is amazing, the Riung 17 Islands national park is mind-blowing both above and below the water.
(It is also one of the only places where dog is eaten in Indonesia, but I could not find that anywhere. We did see a road-crew cooking one over a fire. )
Oh - sit on the left side if flying in by aeroplane… the view of the crater of Gunung Egong is worth it - there was lava when I flew in.
I also went to quite a few places in Western Java, one of my favourites is the tiny isthmus of Pangandaran. I reached this from Yogva via overnight train, it is a pleasant, tiny holiday village with an equally small national park, which features thousands of flying foxes and Raflesia Fatma (the smaller, equally smelly cousin of R. Arnoldii).
Pangandaran also had the best seafood I’ve ever eaten; though the restaurant, as is typical of Indonesia, was just a plastic tent with a few plastic tables!
Finally: Jakarta. It is huge and challenging to get around. It is dirty and smelly. You can get trapped in traffic for several hours without moving more than a few metres. But I really liked it - there are lots of very small, very interesting areas and things to see. If you are reasonably tolerant of packed bodies in the train, that’s a good way to get around the city (easier than driving) and you can hire a tuktuk for short distance travel.
Language: I found basic Bahasa Indonesia incredibly easy to learn. I’d been in western Java for less than a week before I could negotiate prices, ask directions and carry on basic conversations. Obviously the more you try to speak, the faster you will learn, but it is really basic.