1500's at latest. Advances in ship-making,the need for an alternate route to the Spice Islands,Portuguese navigators and even the direction of the Atlantic itself all but guarantees that the Americas will be discovered not too soon after Columbus. The Basque were fishing off the Coast of Newfoundland before Columbus and the collapse of Greenland colony was barely a century old. Europeans know there's a large landmass out there,there's legends about Avalon,Hy-Brasil,Fortunate Isles,Atlantis and Hyperborea, all islands or continents to the west. So,widespread discovery will take place in the 16th century or sooner. Whether or not,it makes Spain dominate for that century depends on the discoverer. Could be Genoa or one of the other Italian City-States,could be one of the Scandinavian countries trying to rediscover Vinland or could be the Portuguese. Frankly,I'm surprised there wasn't a great discovery of the Americas before Columbus considering the advancements made in the 1400's in terms of ship-building and navigation.