For me it would be Garuda, Mandala, and AirAsia.

Mandala is my new favorite airline in Indonesia for now. Their safety culture IMO is the best and they have the youngest fleet in Indonesia. So far most of my flight with them is on-time or even early. But their route and schedule is very limited.

And for AirAsia is like what jpatokal said, cheap and safe, but you have to get used with their retime thingy. Take their early morning flight is your best bet.

So far I've always had bad experience with Lion Air, so I won't use them in the future unless it's really necessary due to their wide network and schedule.