I'm sure I'm coming into this a bit too late but I'd like to build on the comment made by @2012rcampaign & to a lesser degree the answer provided by @abcde.
Essentially, a world the same size or slightly larger than the earth could be made much "larger" from the perspective of a medieval traveler by doing the following 3 things:
- greatly reducing the amount of surface area covered with large bodies of water
- more evenly distributing what's left over the surface of the planet
- dispersing mountain ranges more evenly (and in smaller groups) across the planet
The overall amount of available water would have to be decreased AND I would recommend flattening out the surface relative to the areas of the planet that might (such as on earth) be covered by ocean...
Currently the continents on earth are like very large islands, which we live on the top of, when you consider the depth of the part of our world now covered by oceans.
If you flatten this out, so higher land like the continents, would not exist, or would be very rare then this produces much more area that must be traveled.
In the absence of enough lower land, less water would likely be needed to provide enough for the sustaining of life because it could be made to be available across the entire world... where now the water generally runs off into the oceans and is lost until it evaporates and returns (sometimes) to the contents as precipitation. So replace the oceans with many relatively shallow lakes spread fairly evenly across the world.
The presence of many lakes, rivers, vast marshes, & other water features in place of oceans, might provide enough evaporation for a fairly normal water cycle (water evaporates from the surface so it might be possible to have 45% of the surface covered with water without having large concentrations of water, along with the evaporative effects of much larger areas of vegetation).
If there were no large oceans & the general level of the surface of the planet where flattened out, there could be vast areas of very difficult terrain including:
-Very large marshes/swamps
-very tall seeming mountain ranges (the mountains we generally think of are all on top of contents which are nearly mountains themselves from the average depth of the ocean floor... so take away the contents and have a few mountains reach up past where a content would have reached... this would effectively be very tall mountains...)
very broad, long, slow moving rivers (with less of an incline toward an ocean both longer, more broad, & slower could be possible... though none of it guaranteed given that there would/could also be many lakes, swamps, etc...).
Finally you may actually have to more evenly disperse mountains into smaller mountain ranges, which are also spread more evenly across the surface of the planet.
Mountains provide runoff of snow and a condensation point for clouds (precipitation often occurs around mountains as, if I remember correctly, clouds are pushed up by the movement of atmosphere being deflected up by the presence of the slope of the mountains...[colder thinner air, as I understand it, can hold less moisture).
If the mountains are more evenly dispersed then having many more bodies of water would be more believable as would having an overall greater 'flatness' to the world.
Sounds like an interesting story, good luck!