Well, North American colonization would have been different.
First, think about how Vikings vs Beothuks turned out. The Vikings, with steel, warships and armor, were completely crushed by a force using mostly wood, animal product weaponry and the canoe.
Native Americans at the time had the numbers, the knowledge of the land, and experience fighting in North American conditions. Basically, if they choose to resist colonization, the colonists are screwed with medieval technology. The reason the natives were overcome OTL was because much greater levels of settlers landed, native americans died out en mass from disease.
Europeans were less numerous, so they probably weren't looking for land alone. The reasons for settling would have to be economic. For example, there's evidence the Norse traded with the Dorset for ivory, and interest in North American shifted when elephant ivory became more available. Europeans could also be interested in slaves; in Eastern Europe slavery was rare because the church wasn't a fan on Christian slaves.
Basically, I think that trading posts could be feasible. Large scale settlement won't happen until Europe reaches higher population; so the earliest I see settlement is just prior to the Black Death.
By this point, European diseases would probably have spread among the natives through the trade routes, and they'd have become more disease resistant. Bad news for Europeans interested in taking over the continent.
Also, a lot of areas that do end up with European-style settlement would be Metis in nature. OTL a lot of Europeans defect to native tribes as they found conditions there more pleasant that Europe, and Europeans aren't likely to bring their wives on trading missions.