The Universalior Cogniti Orbis Tabula Ex Recentibus Confecta Obsevationibus (Universe known world map from recently made observations, I think), by Johannes Ruysch, 1507, is hands-down one of my favorite maps.
Just look at it! First, note that there is no large region that has been left out of the top--this is a conic projection that has been "slit" down the side to flatten it into a map, my second favorite projection after pure polar projection. And when you realize that no big chunk has been left out, then you realize, oooh, that the coast of North America and coast of Asia are one and the same on this map. If you look closely, you can find "Tebet", and north of that, the land of "Gog and Magog." To the east of that, "Nova Terra" looks rather like Massachusetts (or perhaps Nova Scotia), and north of that Greenaland merges into North America. Between Greenland and Iceland lies a tiny dot, most likely Frisland--an island that appears on many old maps, often complete with cities and towns, but never existed. Between Greenland and Massachusetts, if you look closely, lie two half-moon-shaped islands, close together. These are the islands of Hy-Brazil, also mythical, whose name was later given to the country of Brazil.
Further south, we have "Spagnola" (thought to represent Japan,) part of the coast of Cuba, and a good chunk of the South American coastline.