If we assume the Portuguese aren't travelling Africa's coast and the Spanish don't sponsor an Italian's wild goose chase, the obvious point of first contact is North East America. Especially given that the Vikings had already achieved that, and the allegations that fishermen were already travelling there.
But what might prompt them to take the next step and explore or settle the East coast? The most obvious prompt I can see is simple competition for access to the fisheries- even IOTL this was subject of violent contention between the French and British. No doubt some monarch will sponsor an expedition to see what lies South at some point. It's not a given that any early European efforts will have as much luck as the Spanish conquistadors did however, and any Caribbean colonies will be relatively stagnant without the importation of slaves from Portugal's African colonies. So the early transatlantic relationship is likely characterized by selling of advanced technology(mostly weaponry) to Mesoamericans and Northern tribes in exchange for luxury goods, and of course ravaging of the Grand Banks. No doubt forts are established in a bid to secure or monopolize trade routes...
Even if the Mesoamericans dodge that early bullet, they're not necessarily in the clear. The east coast will at some point see European settlement, assuming it doesn't early on- whether state sponsored, or independent efforts makes little difference. The important point is that with such abundant fertile land the settler population is going to boom much as it did IOTL. The point I'm making is that it'd be much easier to supply a campaign in Mesoamerica once the invader in question has a solid demographic base further North.