Itinerary 6-8 weeks

Visa: Since you have plenty of time, I'd try and get a 60-day visa ahead of time at your nearest Indonesian Embassy or Consulate. Otherwise buy a 30-day visa that is extendable for another 30-days. Just be aware that extending in places like Denpasar, Bali can be time consuming and if you have an agent do it for you, expensive. Try for an Immigration Office in a less popular destination. A search on this forum gives several options for quicker, less expensive options. However, your timeframe and interests might lessen the options.

Itinerary: Given that you are a 1st-timer in Indonesia you might want to focus your sights on the three major islands: Sumatra, Java and Bali. On 1st thought, 6-8 weeks might seem like a long time and certainly more than many people can get as time off of work, but that time can go surprisingly fast in Indonesia. Personally I would take the full 8 weeks and choose only 2 of the major islands. I tend to travel slowing and prefer to soak up the culture of the islands I visit rather than take a quick look and head onward. As a 1st-timer and young, you may prefer to travel faster and can probably consider all 3. Just remember that travel takes longer in Indonesia especially if you plan to take as few plane flights as possible. If you are more adventurous you may want to skip one of the "big 3" and include Flores and Lombok. Or go really adventurous and do as bigal1 suggests and head straight for Flores and make your way back to Bali. Or really go out on a limb and head for the Banda Islands and then make your way back to Bali via Ambon, the Northern Maluku Islands and maybe Sulawesi. However, the more off the standard tourist trail you get the less party time you will find and travel time slows even more, especially without flights.

Read a guide book to narrow your focus and then come back with more specific questions about where to go and what makes sense within your timeframe.

@thrive, as much as I love Maluku, I wouldn't recommend it to someone who has finding lots of other travelers to hang out with as one of her priorities.

As for adding Sumatra, I think the main reason fewer people do it these days is that it requires extra flights. Sumatra's main attractions are up North, Java's to the East, leaving a long stretch of southern Sumatra and western Java to be flown over (probably requiring 2 flights) unless one is ready to travel looooong distances overland through an area of relatively limited interest.
In fact Sumatra is cheaper to combine with Malaysia than with the rest of Indonesia, though of course easily deserves a trip on its own, too.

In contrast, if adding Nusa Tenggara (Lombok, Sumbawa and Flores) to eastern Java and Bali, one can just hop from one place of interest to the next by train, bus or boat every day. The only flight needed would be to get back from Flores to Bali.

There is a daily Medan- Yogyakarta flight that is available from around 900,000rp, which continues the banana pancake trail entirely seamlessly. It is very popular with tourists - you fly in from Europe to Kl, Singapore or Bangkok, onto Medan directly and thence to Yogya. As Indonesia lacks flight links from Europe on the whole you are probably flying to Indonesia from Malaysia or Singapore anyway, so at least part of that is moot.

Surabaya, Bandung and Jakarta are the other main links east from Medan with multiple daily flights.
There is also a thrice weekly Garuda haji flight via Makassar but I'm not sure if you can book it easily.

@thrive, as much as I love Maluku, I wouldn't recommend it to someone who has finding lots of other travelers to hang out with as one of her priorities.

I agree, which is why I mention right afterwards that "the more off the standard tourist trail you get the less party time you will find". I have met a few people who like diving right into the "less traveled" routes even in new destinations. However, I also doubt it is the what the OP wants. I was just adding it as a possibility just in case the OP gets the bug to try something outside the usual box.

Thank you all so much for this information. And of course I am planning to read guidebooks, lonely planet 'Indonesia' is already on the way!

About the visa-thing, I will try to arrange it before my trip.

And I'm aware the interests I gave are common in Indonesia. I just wanted to hear your opinion and experience. So if you come up with another great have-to-see location, please let me know!

Thanks all for the good advice, when I have an itinerary, I will post it again to see what you think about it.

Why go via medan if going to Yogyakarta. I can see the point of working down through Sumatra

From Europe there are plenty of flights to Jakata and Bali true for many they are not direct but many offer a simple connection in the middle east

Well presumably because you want to visit the Medan area and you want to visit the Yogyakarta area. Working down through Sumatra is time-consuming and most people prefer a 'greatest hits' package; and from Padang there aren't the same choice of flights as from Medan.

It's logistically simpler to fly e.g. London-KL-Medan, than to fly London-Dubai-Jakarta-Somewhere Else, because Jakarta doesn't hold too much appeal for most tourists, so you end up with three flights rather than two to get to your starting point.

Well Ashley is from Holland, not England, and her country has direct flights to Indonesia.
And she has never said she wanted to visit the Medan area, she simply asked for a "reasonable and efficient itinerary" matching her interests, and I think that means an itinerary that packs in a lot of diverse attractions as well connected to each other as possible.
Of course visiting North Sumatra is possible and interesting, but so are many other places situated more closely together. I suggested an itinerary taking in several different islands yet involving relatively short overland journeys and a minimal amount of flying.
But of course it's up to her to decide where she wants to go and how.

Well Ashley is from Holland, not England, and her country has direct flights to Indonesia.

England has direct flights to Indonesia, also. London - Jakarta and Amsterdam -Jakarta are both operated by Garuda.

Of course visiting North Sumatra is possible and interesting, but so are many other places situated more closely together. I suggested an itinerary taking in several different islands yet involving relatively short overland journeys and a minimal amount of flying.

No, you specifically said that to visit Sumatra requires 'extra flights', and 'probably 2 flights' from N. Sumatra to E. Java.

This was totally wrong; your proposed itinerary was something like:

AMS-KUL/SIN-SUB/JOG, then overland to MOF, then MOF-DPS-KUL/SIN-AMS

That's five flights, 15,369 miles

Compared with: AMS-KUL/SIN-KNO, KNO-SUB/JOG, then overland to DPS or LOP, then DPS/LOP-KUL/SIN-AMS, which is also five flights. 15,328 miles (from LOP, just a fraction less from DPS)

For the first time come to Indonesia, as indonesian my suggestion :
- your home country to Jakarta + Bogor (2-3 days) - recover from your jetlag: museum in Jakarta, Taman Mini Indonesia Indah etc. Full day in Bogor (no need to stay in Bogor) : Bogor Botanical garden, Cipanas, Taman Safari Indonesia etc
- Jakarta to Yogyakarta (by train or plane) : Borobudur, Prambanan, Merapi Volcano etc
- Yogyakarta to East Java (by train, bus or rent car) : Bromo volcano, Ijen Crater (Banyuwangi) and another beach in Banyuwangi
- East Java (banyuwangi) to Bali : there are many interesting places and attractions
- Bali to Lombok (by plane or speed boat) : Gili Trawangan , Kuta beach lombok and another beaches, 3-4 days Trekking in Rinjani
- Lombok to Flores (labuan Bajo or Ende) : Kelimutu, Waerebo village, Komodo island, Padar island etc
- Labuan Bajo to Bali . Departure from Bali
If you travel with group it will be much cheaper because you can share cost for rent car especially in Java also live aboard in Bajo . Travel solo in Bali is the most easy than other mentioned locations.
Happy travelling !