First of all, there’s no real need to pin down a specific size of paper, or type of material/medium for that matter. You'll adapt to what is needed at the time, just make sure you have options available. I've played various games using A4, A3, A2, whiteboard, a TV screen and at one point a glass table on which we drew with whiteboard markers while using cheetos and funions as props. And I can truly say that these are all great options, except for the props getting 'lost' on that last one.
In determining a good size or the most suitable type of material/medium, there are a few things to consider;
TL;DR: I'd go with A2, but there are other options altogether.
Miniatures & Party size
Miniatures force you to go big in terms of the map's physical size as you cannot really scale down. And of course, the number of PCs you need to accommodate is also going to drive up your requirement. Using smaller tokens or just marking player positions has never really worked for me, it just isn’t the same. When drawing at 35mm scale, you will run out of room on A3 sooner than you think. That is especially true when your players get tactical, which brings us to;
It sucks having to pause the action to add additional sheets because one of your players wants to see whether he can circle around ‘those trees to the side’. Some GMs would say; “Well, that’s just the map boundary.” Come on, really? I prefer to avoid this type of ‘confinement’ and have the players feel like there is an actual world outside of what has been drawn. If there’s a group of trees, of course they can go around it to sneak up on someone. Just don’t blame me if at one point an NPC has the same thought... → See my additional remark at the bottom.
This is why I usually advise people to go with A2 size when using paper. Large tear off pads are affordable and available at any office supply store. Even if this seems big at first, trust me and just start in the middle. Don’t fold them over to make room, you’ll regret it!
There are other choices if you are not dead set on using paper, but it depends on your set-up. By which I mean the actual table at which you are playing. If there’s enough room so that players won’t be leaning on or putting their drinks/food on the edges of the map, you might consider putting a whiteboard on the table. These are available in sizes more than large enough for any battle and are perfect for drawing on the fly because mistakes a easily corrected. Even better is a smooth synthetic tablecloth, they are available in white but you can also go with transparent as long as you put something under it to provide contrast. You can draw on them with whiteboard markers and they clean very easily.
Additional thoughts on roaming players
The way I go about handling it is best compared to how you can roam about the Battlefield multiplayer maps. You are confined to the general battle area although you can still see a large rendered world beyond that. A player that leaves the immediate area of the battle not only risks being at a tactical disadvantage due to losing line of sight, he risks not getting back in time in case the battle goes pear-shaped. If your map is small enough for him to not run those risks, you should give him some leeway and expand the territory.
When I do not feel like adding additional paper or expanding the drawing, I discuss what the player is trying to achieve and give him the parameters. If he for instance wants to flank as per the earlier scenario, I just tell him how long it will take or what the distance is, what he encounters and where he'll pop up back on the map. Sometimes I also add an additional risk by declaring a 20% chance of attracting unwanted attention or running into an otherwise dangerous situation.
If this still results in your players wanting to explore more than the map you have in mind, just sit down with them and discuss their intentions. Outside of battle or when I do not feel like unnecessarily expanding my drawing, I mostly just describe their surroundings in detail so they can roleplay until they hit a point where they have an encounter with someone or something and it is important to know who is where exactly.