For lengthy voyages, the necessary components are, self propulsion in the form of sails, some form of navigation aids so they wouldn't sail in circles (like a compass, though sun observations can be used), strong discipline in the crew to keep the ship operational, and the ability to carry enough food and especially fresh water to keep the crew sustained.
Wood was the logical choice for construction - medieval humanity didn't have any other material they could work with, that could produce a ship that could withstand a storm.
Size... the larger the ship, the larger the crew, the more food and water needed. The ships that Columbus used were fairly small - the carrack Santa Maria was 62 feet long, while the Nina and Pinta were even smaller.
Guns? Not a lot needed, because the civilizations they would run into were unlikely to have anything like a cannon. The Santa Maria carried four 90mm mortars, plus early muskets. The sound of a cannon alone would probably frighten off anyone they would run into.
In medieval times, they didn't know about dietary requirements, so a lot of long voyages lost crew to scurvy from vitamin deficiencies, and navigation aids weren't very good because where they were going was largely uncharted - they didn't know where the next land would be.
The truth is - many of those very early voyages were 'hail mary' affairs, where they sailed off, not knowing what they would find, or even if they would find anything before their food and water ran out. And there was still a strong belief that the world was flat, and they might sail 'off the edge'.