The number of possible itineraries among the thousands of islands of Indonesia are quite simply unlimited. I don't even try and suggest itineraries covering several regions of the country, instead will provide one week, two weeks and four weeks itineraries for all major regions. You could combine several of the shorter ones to make up a longer itinerary covering various parts of Indonesia, though note that unless you fly from one region to another, you also need to allow enough extra time for getting around by sea.

As I have given more detailed itinerary suggestions for the East Indonesian regions of Maluku and Papua on separate pages, they are not covered here.

                                                                                  ONE WEEK

BALI & NUSA TENGGARA
1. Stick to Bali, splitting your time between a few days on the beach, and a few spent to explore the various parts of the island on a series of day-trips out of Ubud.
2. If you are prepared to sacrifice relaxing on the beach, you could also hop over to have maybe 2 days looking around Lombok.

JAVA
You could see Yogyakarta, Solo and the nearby temples including famous Borobudur and Prambanan, plus Gunung Bromo in East Java.

SUMATRA
1. Fly to Padang to see the Minang Highlands of West Sumatra based in Bukittingi and/or Lake Maninjau.
2. Fly to Medan to see North Sumatra's Lake Toba, the Karo region around Berastagi, and maybe the orangutans at Bukit Lawang.

KALIMANTAN
1. See Banjarmasin, plus Loksado and Negara in South Kalimantan.
2. Visit Kutai National Park and maybe Tanjung Isuy on the Lower Mahakam.

SULAWESI
1. Fly to Makassar in South Sulawesi and head for Tanatoraja, maybe stopping in Sengkang to see Lake Tempe on the way.
2. Fly to Manado in North Sulawesi to visit the Bunaken Marine Park, Tangkoko Nature Reserve, and perhaps climb a volcano.
   
      
                                                                                TWO WEEKS

BALI & NUSA TENGGARA
1. Explore both Bali and Lombok at a more relaxed pace. A week on the latter would allow you to climb Rinjani, see the sights in and around Mataram, the craft villages in Central Lombok, and still have 2-3 days on the beaches around Kuta in South Lombok or in the Gili Islands.
2. If you want to see Komodo, fly to Labuhanbajo on Flores, then either visit Komodo on your own and island-hop back by bus and ferries to Lombok, or take one of the organized boat-trips that visit Komodo on the way from Flores to Lombok. You should still have a couple of days on Lombok and Bali.

JAVA
Add visiting the ancient temples of Dieng Plateau or Gedung Songo in Central Java, Malang before Bromo, and maybe a stop in Baluran or Alas Purwo National Park to the one week itinerary described above.

SUMATRA
1. Do the classic overland route from Medan to Padang to combine the 2 one week itineraries above.
2. Visit Berastagi and Lake Toba, then head north to Aceh to visit Gunung Leuser National Park around Ketambe, and then Banda Aceh and Pulau Weh.

KALIMANTAN
1. Visit Banjarmasin and Negara in South Kalimantan, then Kutai and the Mahakam River in the East. You should have a few extra days in the Mahakam, perhaps enough to get upriver as far as the area around Melak.
2. Sticking to East Kalimantan, you could spend a week visiting the Mahakam and Kutai, then head up to Berau to visit the Sangalaki Archipelago for some outstanding diving or snorkeling.

SULAWESI
1. Explore South Sulawesi in more depth by adding places like Bantimurung and Bira, and maybe the Kajang area to the one week itinerary. You could also visit Mamasa in West Sulawesi.
2. To get off the beaten track in North Sulawesi, add visiting either the Sangir Islands or Bogani Wartabone National Park to the one week itinerary for that area.
   
      
                                                                                 ONE MONTH

BALI & NUSA TENGGARA
1. Four weeks would be enough time to see Bali, Lombok, Sumbawa, Komodo and Flores quite comfortably. This trip is best done by starting with a flight from Bali to Maumere in Flores though, and travelling back to Bali overland.
2. If you prefer more off the beaten track islands, fly to Sumba, Alor or Timor, then cross to Flores by ferry. From there you could island-hop west back to Bali, though you will have less time for Bali and Lombok this way.

JAVA
You could easily travel the whole length of Java in four weeks. Starting in Jakarta, visit Bogor, the Gede-Panggrango or Gunung Halimun National Park, Cirebon, Gedung Songo or the Dieng Plateu, Yogyakarta and Solo with the nearby temples, then Malang and Bromo. You may even have time left to visit the Ijen Plateau, or one of the three national parks at Java's eastern end.

SUMATRA
You could definitely see all the main attractions of Aceh, North and West Sumatra in four weeks.
If you don't go all the way north to Banda Aceh, you could also add a side-trip to the exotic off-shore islands of Nias or Siberut, or head further south to Kerinci and Muara Jambi, or east to Riau.

KALIMANTAN
1. You could travel all the way from Banjarmasin in the South to the Sangalaki Archipalago in the East, allowing longer on the Mahakam River.
2. After Banjarmasin, you could travel westwards to explore the largely untouristed provinces of Central or West Kalimantan - though probably not both!

SULAWESI
You could travel all the way from Makassar in the South to Manado in the North in four weeks. The standard tourist route is Makassar-Rantepao-Tentena-Ampana-Togeans-Gorontalo-Manado, but you could add a few other places, especially if you are ready to skip the Togean Islands.