Bali is a minor Hindu nation, releasable from 满者伯夷 and independent from 1500 start.
Bali can form Malaya.
The 满者伯夷 Empire collapses as of Jan 1., 1500 and Bali appears as an independent OPM with the capital province of Bali-Lombok. Starting in 1500, Bali and other Chinese technology group nations are in an awkward situation: they have the sufficient technology for the first idea group, but the player cannot choose it, and for Bali it is predetermined as Trade. While the group is selected, no individual ideas are unlocked and so the player can simply choose to abandon the idea group. Since no ideas are unlocked, no points will have been lost. It then advisable for the player to pick up Exploration ideas as they are crucial for Bali.
Bali's first conquest is likely to be 望加锡. While the player can declare war right away and take the -2 stability, this will be difficult due to the necessary amphibious landing and Bali's weak initial economy to support an overwhelming number of troops and transports to ferry them. Landing on the uncolonized native territory is not recommended: the natives do put up a decent fight against a player with MIL Technology 4 Chinese units. Consider that many colonizable provinces in Indonesia and the Philippines have a fairly high number of aggressive natives. However, this also means that if the player wins the first battle and defeats Makassar's army, the defeated army will retreat into native territory and be destroyed there. A safer way is to settle a colony in the adjacent territory and launch an attack from there.
If the player mods the game to have the Exploration ideas chosen as the first idea group, a colonist can be sent around the Spice Islands right away, although the islands east of Java are not the easiest place to colonize initially. Most of the archipelago is covered with terra incognita, and while the natives in Java can be difficult to deal with, the development from there can be very valuable. The initial re-settlement of the Spice Islands will require full military support and the stationed troops can still lose, if the aggressive natives spawn in short successions. Since all the islands west of Irian (Papua) do not count as overseas, full development increase can be expected from these provinces, although it also means overextension and normal coring cost in the mean time.