Did you go to war with British to get NZ and, if yes, when and how it happened?
No, I rolled for an empty Oceania, it's surprisingly more reliable. Putting the cities down yourself ensures you get the rest of the build going smoothly.
Speaking of, Hobert could be slightly reduced on the English settling map, to a 8 or a 5. It's fine to start with it from time to time, but I saw it often and Melbourne is the objectively better spot.
Anyone here pulled off UHV1 on Regent/Normal while starting with no settled cities? Need tips.
The easiest way out is to put as many Mines as you can with the Advanced Start, as they will both spare you working turns, but also speed up the production of the cities you're going to put there. Of note, you can get one extra Aluminium mine by using the Advanced Start to clear the one in the jungle on Cape York, which will get you to 17 — the last one can come from either New Zealand or New Guinea, or any close-by city you can reasonably take with your starting army.
You start with 4 Settlers. You want Sydney, either Adelaide or Melbourne, Perth and, if possible, Auckland, and each of these cities should start with a Settler > Worker build (though there are variants, don't be afraid to experiment around). The rest is natural settling over the island, trying to get to 18 mines in time. Have your cities work Culture to get mines in range (especially important for Perth and Wagga Wagga) and don't be afraid to go to 15 Workers or so. Forget making units, they're not going to be useful, you can draft city defenders a bit later. Forget buildings too, but you might get a wonder with your Great Engineers if luck is on your side : Bell Rock Lighthouse and Statue of Liberty are the two big ones.
Also, mind the Worker use ! Start by cutting woods to get faster production, don't let them waste turns if they are in a stack, and don't keep them idle ! Your Steamships can balance them out across, moving half of them out of an area that is almost complete.
For the technologies, start with Electricity to ensure Aluminium is available by the end of the UHV. Collectivism is better, but it can be difficult squeezing them both while you're still figuring out the ropes.