New Spain was a no-brainer (VH/VH, huge units). You should ally with the Aztecs. This alliance allows you to hire Arrow and Eagle warriors, who are very strong in attack and defense ratings. I traded for their province to the south that becomes Vera Selina for a few thousand florins (I don’t recommend an exploit, since you will always have lots of money and the scenario is a cakewalk) and later Mictlan as well.
Have Hernan take the two rebel settlements to the east by siege, while you train a war galley and some units in Havanna. One of the generals from Havana should go by ship to hire Arrow and Eagle mercs (they are available around the bridge east of Vera Selina) and pick up Dismounted Conquistadors trained in your settlements. Now send these three armies to the northern coast of the region controlled by the Maya and lay siege to all three settlements there at once. You can hire more native mercs as well to fill up your stacks. I had looted half their empire before they could react. On turn 14, Montejo shows up with another force and by turn 21 the Maya were no more. Snap up the last rebel settlements to the south and east. This gives you about a quarter of the map. I kept the Aztecs as allies so that I had access to the best mercs and then crushed everyone else.
'Olé!