Civil Islam by Robert Hefner (2000) is a history of Indonesia after independence, with particular emphasis on Islamic political parties. Early Indonesian history is rather sketchy here (I haven't read his references), but the progress of Islam across Indonesia was associated with some violence, though whether more than usual I can't say. The large volume of trade (pre-Portugese) made the area much more diverse (and coastally cosmopolitan) than one might have expected.
Hefner's thesis is that democracy arises from a civil society with a civilized state, and that efforts to produce democratic structures were thwarted and corrupted by power-hungry dictators. The result of playing one group against another has been increasing violence and a breakdown in civil discourse which might otherwise Modern Indonesian history is rather grim. Thanks to occupations, there arose effectively a shadow government, which after indepence was centered in the armed forces. As they took control of various state economic enterprises, their power became quite extensive. Hefner does not address this power base as much as it deserves, largely because of the lack of information about it. Soekarno taking the reins early with a Javanist, Communist, and Muslim "coalition." When the Communists overreached themselves in 1965 they were exterminated, with half a million dead. Some Muslim groups afflicted by the Communists were closely associated with the campaign. Political Muslim groups had been suppressed, but parties developed anyway, some in conjunction with pro-democratic reformer and some more conservative. Some of these parties wanted the idealized Sharia-state, but others advocated a more plural society.
A large fraction of the Muslim population was syncretic in religion, mixing shamanist beliefs with the usual Islamic ones. Thus there was already a large constituency for a less-strict Islamic society. With the largest Muslim political parties suppressed, many Muslims turned their energy to more peitist concerns--in particular trying to convert the pagans and purify the religion of their nominal fellow-believers. Over time this increased the number of conservative sharia-seeking Muslims.
After Soeharto succeeded in deposing Soekarno, he maintained his power by playing one group against another, by co-opting some movements, and planting his relatives in positions of economic power. He and his clan stole incredible amounts of money. In the 80's he thought it advisable to shift support away from the Javanists and to Muslim groups, which began to rise to much greater prominance. The details of the power struggles don't make pleasant reading, and I'll spare you them. It began to become clear to several of the groups that they were being used for purely political ends, and had been back in 65 as well; and one of the larger parties took as one of its guiding principles that the union of the state and Islam ends by subverting Islam to the service of the state.
Unfortunately this epiphany was not shared by all the Muslim parties, and some of the familiar sharia-forever groups also became prominent. Hefner thinks military and Soeharto-affiliated groups' dirty tricks teams as the ones to blame for the radical escalation of violence that marked Soeharto's last years in power, and thinks that the continuation of that violence is due to the military factions and the legacy corrosion of civil society. Even today if someone comes close to trying to trace Soeharto's stolen money, people are bribed, violence flares somewhere, or something else happens to divert attention. $15 billion can buy a lot of trouble-makers. He suggests that the East Timor violence was one such diversion. Even if so, the implication is that a significant fraction of the population and the armed forces are willing/eager and available for such hateful outbursts.
OK, my overview of his conclusions: We know the jihadists are there--we knew even before the Bali bombing. East Timor, Ambon, and many less widely publicized incidents told the world that. Hefner attributes some of this to the legacy of manipulation and violence by brutal rulers. Maybe. However, he shows that there exist Muslim parties with less than all-encompassing aims (and in a 90% Muslim country), some with a commitment to democracy. He tries to show that these developed from native civil institutions and customs, but actually doesn't give a lot of detail to support this (a shame, since I think he's right).
Reading about parties forming and dissolving and allying and backstabbing all in an environment where shaking hands with the ruler is a really big deal--makes me very tired. Enlightened, but tired. Yes, read the book.