From a cursory read on the subject:
I can see America being discovered in the Middle Ages, but likely not colonized in that time frame. The Spanish Conquests were a combination of luck, disease and the conquistadores taking advantage of the weakened Indian positions. Without them conquering huge swathes of well organized territories at once (the Spanish employed much of the native infrastructure to assist their rule and settler colonies probably very small (no reason to go that far away except for fishing outposts and trading), that leaves out the first possibility of an European empire on the Americas. While the cultures at that time in the Americas weren't that unified, I'm confident that they could resist an invasion, even when weakened by plague. In fact, the lack of resentment against empires (most of Cortéz success, for example was by courting enemies to the Aztecs) might prompt them to unite against invaders. From the sources I found, Mesoamerica and the Andes had already city-states. I need to do more research on that.
So, Europeans IMO would have neither the means or needs to form empires. They would visit the Americas. Fishing colonies are a posibility. Trading ports even more so (I'm not sure when the Mesoamericans started using gold, but that would be one of the first places to start trading due to geography. The Andes are far off). Plantations? They would need to secure territory first. The mainland would be hard to secure without technological and allied advantage. The Caribbean islands... maybe, but, did the Europeans have sugar or cotton to be planted there at this time? Can anyone enlighten me?
Someone would inevitably bring up the crusaders, but crusades to America would be logistically akin to crusading to India or China, and probably with less of a payoff. Not to mention the focus of crusading would still be on the Holy Land.
Disease will kill the natives, of course, and will provoke huge social changes (many sophisticated societies disbanded in nomadic bands OTL due to their collapse after European brought disease, like those in the Amazon and many others). But without empires opressing the natives and mass colonization, I would see the survival of many indigenous nations. From there, all bets are off.
What is very interesting, however, is the earlier Columbian Exchange. The introduction of potatoes and other crops to the Old World will forever change demographics, same with the New World and other crops that can easily grow in tropical zones. The intruction of horses and European technology to the natives in a more paired scenario would be very intersting too.
If someone had the time, research and creativity, this could be an excellent TL