If one is aware of the dimensions of Africa is the key, indeed, like you say. The important information is how far south does Africa extend, so that it can be circumnavigated. Still, there's a preliminary question that your modern mind answered before... is it possible to sail around Africa?

During the 15th century, Ptolemy's Geography was rediscovered in the Latin speaking world, which was also refining its cartographic skills based on the mediterranean navigation. Ptolemy's world, however, had Africa extending south into "the unknown" (you may well read, the south pole), making it impossible to cross from the Atlantic to the Indian Ocean. Here's a map of 1482, made in Germany, based on Ptolemy. As you can see, the Indian Ocean is closed.. this map wouldn't excite an explorer to go from Europe all the way to the south of Africa, not to reach India.

But. While cartography had its rules as a starting science, there was some liberty for the cartographer. At this time, a lot of the map depended on which sources you had access to and which ones you selected to believe in. Legends were abundant. A different map would show the south of Africa in a completely different way. Fra Mauro's map made in the 1450's, for example. This map was done in two versions and one was commissioned by the portuguese kings. Indeed, the portuguese were the first europeans to circumnavigate Africa, but they didn't do so until 30 years after this map was produced. Other from factual knowledge that informed the mapping of Europe, North Africa, the Middle East, there were only the odd traveler accounts (Marco Polo's book, an Ethiopian delegation to Rome, etc.) and cosmological ideas. One such cosmological principle in this map is that land is entirely surrounded by water. Still, this is a map that invites exploration southward.

And when Vasco da Gama was only 10 years old, european (portuguese) explorers reached the southern tip of Africa. Secrecy and deception were law in Portugal, in everything related to the voyages of exploration, and when news couldn't be withheld, they could be bent. The fact that there was a passage between the Atlantic and the Indian leaked very quickly. Here's a map from 1491, the Martellus map, very likely based on information passed on by the Columbus brothers. What's interesting about this map is that while very accurate in many areas, it fails in a spetacular manner when it comes to the southern tip of Africa. Cape of Good Hope is 10º further south than it is in reality and that is a larger error than the technology of latitude measurements, available at the time, could justify. The theory goes that the map proves how the portuguese kings wanted the rest of Europe to overestimate the size of Africa, deeming it too far a trip to make. This, as it would be impossible to hold secret that indeed there was a passage between the two oceans.