Difficult question and a few things to consider.
1) Do you speak (GOOD) French? If not Mad can be a bit of a hasstle.
2 Remember also that Indonesia is SO diverse. Where do you want to go? Jakarta? Bali? Borneo? Sumatra? These are all different worlds.
3) However the reason I would settle for Indonesia is because I found Mad a pain in the neck in that you couldn't do very much without guides, rangers, drivers etc etc. This is partly due to the poor infrastructure (esp. roads), partly due to the fact that some areas are environmentally threatened, but to a large extent due to a "tourist" industry that seems to be trying to build itself up on accompanied groups. Presumably if I'd had a 4X4 (and a guide/driver) I could have got off the beaten track more (I did try) but then again you need a lot of time as driving over the boulder tracks is torturously slow. And fuel expensive. I must admit that (with 50+ countries also under my belt) I was rather dissapointed with Madagascar last month. They do everything possible to make it as tame and safe as possible. And unfortunately there isn't much to do in the towns either ("people-watching"? - yawn).
So if your a free spirit, like the great outdoors and want a bit of adventure I suggest Indonesia.
I wonder if marogisa, who is obviously a great and passionate fan of Madagascar, has ever been to Indonesia and thus can compare the 2 countries meaningfully.
To say Sumatra is a monocultural wasteland is simply not true.
Anyone travelling there will see lots and lots of rainforest left even outside national parks (which BTW are huge, often several thousand sq kms, much bigger than any park in Madagascar), and will find that even cultivated areas are mostly very pretty, far from monoculture.
Further east, MUCH of huge regions like Papua and Maluku are largely pristine naturally.
Now, I did travel a fair bit throughout Madagascar, and saw extremely little forest outside (mostly fairly small) national parks. And most of the deforested areas were left to turn simply into unproductive grasslands, or scrub.
As for the flights, I was told by a friend living in Madagascar that the reason airfares are so high is that local government officials travel for free and tourists have to pay to keep the airline afloat. I didn't check this this myself, simply believed it.
Whatever the reason, in Indonesia a domestic flight crossing 3 time-zones from Java to New Guinea costs significantly less than a much shorter flight within the same single island in Madagascar. And most passenger happily survive their flights.
As for the cultural diversity, while the people of Madagascar are officially divided into various "tribes" in fact they all speak dialects of the same language and pride themselves on a shared culture. Sure, there are subtle differences, but most of those are not obvious to tourists.
In fact most tourists I talked to said that they were disappointed with the "lack of culture" (as they could see it) in Madagascar, probably because people don't wear colorful ethnic custumes and practice readily seen ceremonies.
I myself was lucky enough to see various traditional ceremonies in Madagascar, both a mass reburial and 2 spirit calling ceremonies up north. But still, for very obvious reasons already stated even by our passionate Madagascar fan, the diversity and colorfulness of traditional cultures in Indonesia is one matched by very few other countries - if any.
To round it up, I would say that obviously BOTH countries ARE worth visiting. But the question here was which one is more so, and to that Q, my answer can only be Indonesia - unless one wants to see lemurs (or study Malgasy, etc - but that's far less likely).
And this is not only about Madagascar - given Indonesia's extraordinary diversity in cultures and nature, I would probably also rate it higher in those fields than most countries in the world, with the possible exceptions of giants like China or India.
OTOH, if anyone ever asks whether he/she should go to Mauritius/Seychelles/Singapore/etc or Madagascar, I will no doubt recommend Madagascar.

Well Laszlo, I can set your mind at rest on your first point. I lived and worked full time for two years in Indonesia, (not, in case you ask, as a company expat, but for an Indonesian organisation) and I took advantage of that also to travel extensively in the country, so you can rest assured that I do actually know what I'm talking about.
The comment on Sumatra is certainly not my own but very typical of what I've heard often enough from people who should know better. I was citing it as an example of ignorant prejudice on the same level as comments suggesting that Madagascar is in large part a deforested wasteland.
As I said, there is a grain of truth behind both of these ill-informed comments: anyone who knows Indonesia at all is well aware that the country has serious environmental problems arising from the destruction of (often protected) ecosystems and habitats to make way for monocultural plantations and illegal logging, and that efforts by conservation organisations both national and international are frequently seriously undermined by the endemic corruption (Indonesia is in 143rd position on Transparency International's corruption index, Madagascar is at 94 – the higher the number, the greater the corruption). To give you a specific example, Bukit Barisan Selatan National Park in Sumatra has, according to WWF, lost fully 20% of its forests to illegal agricultural activity, and well over 400 sq. km of the park is now covered by coffee plantations.
Applying the "grain of truth" to Madagascar, it's undeniably true that large tracts of Madagascar have – regrettably – been deforested and converted to use for cultivation and other human activities. If that makes it into a "wasteland", then by the same token we'd have to define much of Java as a wasteland. It is not, of course, but the gross overpopulation of Java coupled with the prevailing traditions of inheritance in Javanese society is much more likely to tip it over the edge into a true wasteland than what's happening in Madagascar at the moment. To say that the deforested areas have been left to turn into unproductive grasslands or scrub displays a certain lack of understanding of agricultural cycles.
Certainly I'm a passionate "fan" of Madagascar, and would never seek to deny it. I also get equally passionate about Indonesia, but that clearly isn't so necessary here. Nobody on this thread has attacked Indonesia by calling it dirty, depressing, uninteresting and lacking in unique features. Nor has anyone implied that the Indonesian system of national parks is inherently anti-tourist because they don't happen to like the way things are done.
Dirty? Any developing country is dirty if you take the northern world as your yardstick. But anyone who says that Madagascar is “far more depressingly poverty-stricken and dirty than Indonesia”, has either been through Indonesia with their eyes shut or has confined their travel to the more or less sanitized locations on the main tourism thrash, or is for reasons best known to themselves wilfully putting Madagascar down. Anyone who is not able to handle the dirt and poverty that are part and parcel of the entire developing world needs to seriously ask themselves if they want to visit either of these two countries.
Uninteresting? I find it truly astounding that someone who has been "lucky enough to see various traditional ceremonies in Madagascar, both a mass reburial and 2 spirit calling ceremonies" can post on the same thread a statement like "The only unique things Madagascar has are the lemurs". Leaving aside the apparent lack of knowledge of fauna and flora, you contradict yourself.
Perhaps the problem is that it's undeniably much harder work to get to see the culture in Madagascar than in Indonesia. Certainly there is not (yet) any of the sort of "just-for-the-tourists" culture offered on a plate which has become such an unfortunate feature of Indonesia over the past few years. For me, this hard work is part of the attraction, but I can readily understand and respect people who say it is not for them – as long as they don't make entirely misleading statements implying that there is nothing of the kind to see in Madagascar. Surface travel in Madagascar is very frequently hard work, and for the most part not comfortable, and anyone who is not happy with that prospect should certainly choose Indonesia if that is the alternative.
On Air Madagascar: the reason their fares are relatively high is not "that local government officials travel for free and tourists have to pay to keep the airline afloat," but that the airline is a government owned (93%, I believe) monopoly. A further reason may well be that the airline actually pays to have its aircraft maintained to the highest safety standards, a policy ensured by the management (the CEO for the last four years has been seconded from Lufthansa Consulting), which has also implemented a fares policy designed to keep a well-run airline economically viable.
Competition might bring the fares down, but I'd hate the situation in Madagascar to develop into what we have in Indonesia at the moment, where inter-island travellers are forced to choose between the rock of unseaworthy, overloaded ferries and the hard place of ill-maintained aircraft flown in many cases by inadequately-trained crews. Check out the recent safety record of aviation in Indonesia and the causes of the assorted crashes – it's all easily accessible in the public domain.
On "local government officials travel for free" – I don't know if they do in Madagascar, though it wouldn't surprise me in the least if they did, but I know for a fact that they do in Indonesia. However the idea that this might materially affect the fares paid by the rest of us is very strange. There just aren’t that many officials of the requisite status, not even in the notoriously top-heavy bureaucracy of Indonesia.
On "tourists have to pay to keep the airline afloat" – this is what is called paying a fare. I do it all the time when I fly with Lufthansa, British Airways etc. etc. as well as when I fly Air Mad.
Anyway, I'm glad you now agree that both countries are worth visiting, although you can’t resist another entirely unjustified and truly absurd put-down by ranking it just above the Indian Ocean islands and Singapore. Which of the two, Indonesia or Madagascar, is more worth visiting is a question which is as good as impossible to answer, and represents a choice people should never be forced into making. Both countries are going to have their advocates. But it beats me why anyone should feel that the best way to advocate Indonesia is to paint an entirely inaccurate negative picture of Madagascar. That obviously does no justice to Madagascar, but it doesn’t do a lot for Indonesia, either.
The statement about much of Madagascar being "deforested wasteland" may not sound pleasant, but is so obvious I find it hard to believe anyone knowing the country can dare to deny!
Just flying over the country will let one see it easily - driving around the island shows it close up.
Fly over or drive around heavily populated Java, and you will see verdant green rice fields and other gardens for the most part, punctuated by forested volcanoes.
Do the same in Madagascar and you will see patches of fields here and there, mostly in the valleys close to water, then an awful lot of unproductive grassland on the slopes above.
This has little to do with agricultural cycles, if with anything, it may have more to do with both the more industrious nature of the Javanese, and to the fertile soil of that volcanic island. The sad fact is, most of the deforested slopes of Madagascar have lost much of their topsoil and so are unlikely to ever recover or be put into productive human use.
Sure, Indonesia has lots of logging, too.
But overall, it retains far more forest cover than Madagascar's, which is estimated between 3-10% - the latter figure no doubt optimistic, and includes much secondary forest or scrub.
Sumatran parks like Bukit Barisan Selatan are so big that even with parts of them damaged by illegal activities, the rest will still be bigger than parks in Madagascar.
As for who has the lack of knowledge of flora and fauna, or who travelled through Indonesia with closed eyes, I let other TTers decide for themselves. I do have extensive pages, with photos, on Indonesia linked in my signo line, and have a decent count of TT posts on that country at least.
For sure I have spent shorter time in Madagascar, but that was still much longer than what most tourists will, and I have also seen more regions/parks/ceremonies than most (also put much more money into guides' pockets in the process, if that keeps you happy).
I simply dared to compare two very different countries, as requested, in a way that was in fact echoed by several other posters here, regularly attracting vehement attacks/criticism by just one poster: you marogisa.
I think that alone says a lot. So like the others, I will refrain from further useless arguments.
Feel free to have the last word.
I am sure OP has already read enough to make up her mind either way.

@margosia
you're taking this far too personally. Besides, the original post only wants some advice for choosing one country now, and possibly going to the other one another time. I doubt PW wants to know all the political or environmental problems, but just "facts for the traveller" so far. We all speak of our personal opinions, which are by no means the absolute truth, and so do you.
Safety IS an issue in Madagascar. You don't walk around in bigger cities at night, and tourists have been murdered for money in the South (and those were actually well organized and thought through attacks - that's the scary part!), while "only" theft occurs regularly in the tourist spots in the North, aka Nosy Be and Diego Suarez.
You shouldn't be so outraged when others don't share your views. Why do you presume others who posted here have not worked or lived in one or both countries as well? You're quite wrong! Fact is, what I experienced, was what I listet above, and if I could choose to return to one of these two countries, it would still be Indonesia.
Why on earth are you upset when someone claims the Madagassy culture uninteresting? Everyone has a different gusto. I didn't like it much either, I couldn't care less in the end. Twenty men stabbing a zebu to death for sacrifice was neither interesting nor enjoyable to watch, but surely made me avoiding any more cultural intake. Oh, I know similar cruel things happen in Indonesia (or all over Asia, so to speak), but I didn't have to experience it for myself...
I could write about many travel inconveniences I had in Madagascar (Air Madagascar Twin Otter which almost poisoned us 20 passengers with fuel vapours, bush taxis notoriously braking down, weather changes making it impossible to reach my travel destinations etc. ), which never occured in Indonesia, but that doesn't mean it never happens there as well.
One thing though was absolutely impossible to do in Madagascar with locals, but was the experience of a life time in Indonesia: hitch hiking!
berit

Marogisa and Laszlo, thank you very much for your passionate discussion, it gives a great insight into both countries. I've just been to Indonesia for three months last year and I'm looking forward to go to Madagascar this year. Indonesia was one of the most diverse countries I've ever seen and I'm sure Madagascar is at least as interesting. And you are both right in the one important point: It's just not possible to compare two countries with each other in terms of travelling.