Into the Heart of Borneo by Redmond O'Hanlon is the funniest book about Indonesia — a botanist and a poet travel into the interior of Kalimantan with a rakish English poet and a Dyak guide. Brilliant on the jungle, the culture, and the absurdity of European explorers.
The Year of Living Dangerously by C.J. Koch is a novel set in Jakarta during the final year of Sukarno's presidency (1965), a time of coup, massacre, and chaos. It was made into a film with Mel Gibson and Sigourney Weaver. Essential for understanding what Indonesia's 20th century looked like up close.
This Earth of Mankind (Bumi Manusia) by Pramoedya Ananta Toer is the first volume in the Buru Quartet, written while the author was imprisoned without trial on Buru island under Suharto. It is set in colonial Java at the turn of the 20th century and is widely regarded as the finest Indonesian novel. The full quartet is worth reading.
In the Time of Madness by Richard Lloyd Parry is a first-hand account of the violence that accompanied the fall of Suharto in 1997–98, including the mass killings in Kalimantan and the chaos in East Timor. It is one of the best pieces of journalism about modern Indonesia.
Eat Pray Love by Elizabeth Gilbert is set partly in Bali and has done considerable damage to the island's tourism ecosystem, but it remains a readable account of the expat-spiritual circuit in Ubud. Useful as a document of a certain kind of Bali experience, even if that experience is not for everyone.
The Spice Route — for historical context on the Maluku Islands, a good background is Giles Milton's Nathaniel's Nutmeg, about the 17th-century spice trade and the extraordinary violence that accompanied European competition over cloves and nutmeg. The Banda Islands make much more sense after reading it.
Lord Jim by Joseph Conrad is set partly in the Malay archipelago, including what is now Indonesia, and captures the atmosphere of 19th-century colonial trade and moral complexity better than almost any other novel. Conrad spent years in these waters.