I believe that before the Autronesian expansion, Papuan groups were beginning to settle and introduce their agriculture to the west. ITTL the Moluccas, Timor, Sulawesi, etc will all have much greater Papuan influence.
Pre-Austronesian ethnic groups like the Negritos will survive in a larger area.
Madagascar would probably be settled by Bantu from mainland Africa.
I can't see the Papuans ever going further east than New Caledonia and Vanuatu, and even those might not be settled.
Micronesian islands like Palau and the Marianas might be settled by Negritos from the Philippines.
The ramifications of an empty Polynesia will be very interesting, especially with the larger island groups.
I can imagine that places such as Samoa, Hawai`i and Fiji will be colonised earlier than OTL, and when the Europeans (assuming European colonisation isn't butterflied away) arive they will set up plantations with indentured servants from Asia. Kind of like what happened in Fiji and Hawai`i OTL, but with no indigenous people. Tropical Polynesia will probably look something like the Mascarenes today, a multi-ethnic, recently settled, small island society.
New Zealand will be very interesting too. European colonisation will probably be a bit slower due to the lack of trade partners, and maybe some now extinct species will survive.
If they existed, the Menehune and Nawao would have been Austronesian. I'm of the belief that they were probably from the Marquesas, and the modern Kanaka Maoli were later Tahitian settlers.