It baffles me as to why this region had such an impact on the language and culture of the colonies when it was the most recent addition to the continental Spanish crown.
Some questions have simpler answers than they appear to. It is because Andalusia wasn't a recent addition at all.
The Kingdom of Granada, roughly equivalent to the modern provinces of Malaga, Granada and Almeria, was conquered and annexed into Castile in the war of 1481-1492. However, the Kingdom of Granada wasn't considered part of Andalusia until the 18th century. Andalusia as understood before that, or Andalusia proper, was just the Guadalquivir river basin, which included the kingdoms of Jaen, Cordoba (same as the modern provinces), and Seville (the homonimous province plus Huelva and Cadiz). The majority of these lands had been conquered by Ferdinand III (r.1217-1252) over two hundred years before the conquest of Granada and the discovery of the Americas, so there had been plenty of time to integrate them before that.
As for why Andalusia (proper) dominated the American trade, well, it falls down to geography. It is a plain area in the southwest of the Peninsula, with magnificent harbors, a navigable river up to Seville and the most fertile land in the Iberian Peninsula. In early modern Spain, Seville was the largest and richest city in Castile-Aragon, the home port of the Castilian fleet's Andalusian squadron, and the home to a vibrant trading community formed not just by Castilians but also Portuguese and Italians. It was only natural that all matters regarding colonial expansion and administration became concentrated there: it was where the money, ships and merchants were. This was formalized in 1503 with the opening of the Casa de Contratación in Seville. From then on and until the Bourbons semi-liberalized it in the 18th century, all trade between Spain and the colonies was done through Seville, and everyone who wanted to move to the Colonies would have to move to Seville and request permision at the Casa de Contratación. If you were, say, a nobleman looking to mount an expedition of conquest or setlement you might come from anywhere in Spain (or even other Habsburg territories) but you would have to move to Seville and reside there while the matter was formalized. When everything was set, after a period that might last years, you would have to recruit a crew, and since you were already in Seville, you would obviously recruit it there. This is why the Canarian and Latin American dialects of Spanish are actually closer to the Sevillian accent than even other, more western Andalusian ones.