I'm worried about 3G coverage because I am traveling all over Indonesia.
That is: Sumatra, Java, Bali, Lombok, Sulawesi & Komodo.
If you're particularly worried about a specific area, for comparison, I managed to find some coverage maps on Sensorly:
Note that on either of those, you can change the drop down on the right for (at time of writing) five providers, to see their coverage.
I have tried them all over the past years and finally I chose Three for the following reasons:
I used to use Smartfren before that, but it is not GSM and I had to buy a special router for that, credit was hard to find but the prices are less than Three and other providers.
I only have experience of 3G coverage in Indonesia with Indosat & Telkomsel. So I will only discuss those mobile providers.
I tried those providers in remote areas (Sumatra, Java, Bali, Lombok, Flores) and also in big cities. Long story short: Telkomsel wins.
Basically, Indosat is "ok" but I found it to be very unreliable in many places. Going from perfect signal to no service in a short distance (a few hundred meters maybe).
Another funny thing is that sometimes I was next to my friend who also had Indosat, and often I had good signal when she had none! It just didn't make much sense.
After a month of many frustrations I gave up & decided to change.
Telkomsel has the best coverage in Indonesia as far as I know. This is my personal experience and also many locals telling me that whenever I'm outside a city.
I've been to some places where I would not even dare hoping for a signal, but Telkomsel had one somehow. A tiny signal, but a signal.
The only downside is that you will pay a bit more for this. However, many resellers have special data deals cutting the prices as much as 50%, just ask. I always find one after asking two or three resellers. However, make sure the data is valid nationally & valid for any time of the day (not partly for night and other part for the day).
As far as I have been told, 3 is only good in big cities. And the biggest advantage is that, probably because of this big city only coverage, this provider is cheaper. But you won't get a coverage in much places, even the Gili's..!
Not sure about the other providers. If there are any, they must not be wonderful (coverage or price wise) as I haven't heard of them in 3 months in Indonesia.