This...is a very big question to answer. To start, let's look at some history.
Rome divvied up their empire into provinces, but they kept changing them and redrawing them--as of AD 14, it looked like this:
Under Hadrien, around AD 125, it got broken up into more, smaller pieces and looked like this:
But then we get to around AD 300 and Diocletian redraws the map again and dramatically reduces the province count to this:
Even across a single empire, the size and arrangement of provinces kept changing. But then, for even more fun, we drill down to the very, very end of what remained of the Roman Empire--the late Byzantines. You have modern day Turkey and Greece (and a few other bits) as all the empire they have left--and what was, at the height of the Roman Empire, only a handful of separate provinces is now a very large number of Themata.
So, really...there's not a specific right answer here. Provinces are however big they end up being. I mean, look at a map of the States of the USA and how widely varied they are in size (then drill further down and you can see that most of them are further subdivided into counties)--then look at other nations like England where the whole country is smaller than quite a few US States, but it's chopped up into 9 regions and further subdivided into 48 counties.
But, I can give you some pointers to get you headed in the right direction.
How 'controlled' is the territory?
How much of a given territory is actually settled and actively ruled by that empire? Historically, Empires and Nations have drawn with a broader brush when sketching out territories that they don't practically rule. For example, look at the history of the United States. When the American Revolution kicked off, the then-colonies claimed that this was what the map looked like (the red being spots where the states disputed who owned that):
Look at that insanely huge block of land that Virginia claimed. They didn't rule all of that, they had no way to control that much land. They just sat down with a map and went "All the rest of this is ours." And that was Virginia. As time passed and more of that land was occupied, conquered, and 'settled,' the territory got broken off into smaller chunks.
That is a historical example of this case--places that aren't actually, practically controlled by the Empire are often a larger province. Though most of the land being part of the province is just a technicality.
This can also be the case when you have large swaths of 'not useful' land, like desert. Sure, you could break it up into small provinces, but why? Very few people live there, you 'rule it' because it's inside your borders, and it doesn't really contribute to the Empire. Either hack it up into the territories of provinces that neighbor it, or just make it one big province and call it a day.
How populated is the province?
The more people live in one place, the more effort it takes to administer them. Historically speaking, more densely populated provinces tend to be smaller.
"Tend to" being the operative term, this is not always the case.
Are there convenient natural features that make for good borders?
It's easier to draw maps and have concrete territorial divisions based on rivers, mountains, ravines, or other immovable natural features. You can just go "Ok, everything east of this river is yours, everything west of it is mine," and now your territorial disputes are much easier to handle--or are at least smaller scale (you just get to argue about any islands, or which branches of the river are the main branch).
This can also be the case with convenient man-made features--like a major road or a canal, or maybe someone went and built a really long wall.
How quickly can you communicate AND how important is rapid communication?
An important key to holding empires together is the ability to communicate. If, for example, you cannot get news of an invasion to an army fast enough to matter, then you're going to lose a chunk of your empire. Likewise, if laws, rulings, declarations, etc. from the Emperor never practically reach people because communication takes too long, you don't effectively rule that territory.
A largely rural, agrarian territory that is interior to the empire may be larger than one situated along the border that is more at risk of invasion.
What powers do the provinces have?
This is largely a question of the government style of your Empire. How independent are these provinces? How much power do they actually have to rule themselves?
If they have little power, and all you've done is chop your empire up into bits so it's easier to talk about parts of it, track tax revenue and population, and otherwise just keep things organized--then the size of a province doesn't really matter. What matters in that case is how your bureaucracy and military are organized so that you can still respond quickly enough to not collapse due to a lack of communication.
The more independent a province is, the more its size matters. The more powers you give it, the more responsible the province is for maintaining itself, rather than the bureaucracy of the central empire. That being the case, your provinces need to be small enough that they can maintain the communication and control necessary to rule (which will be impacted by your tech level.) But if they are really good at communication and control and they get big enough--they might start getting funny ideas about independence.
So, this is kind of a question of centralized versus decentralized power.
Why were these provinces formed in the first place?
Again, historically, provinces could be formed for several reasons.
- The familiar 'United States' model that had a bunch of semi-independent colonies (or kingdoms or tribes or whatever) uniting into a single nation--in which case the idea of provinces was baked in. In which case, provincial size is however big that semi-independent unit was. And then as they added more...they were however big the politicians drawing the borders thought they should be.
- You are the ruler of the Empire and want to reward your Faithful Subjects with land to rule--in which case the province you give them will be precisely as large as the grant of land you gave that favored minion. Big provinces for greatly favored subjects, smaller ones for the less important subjects.
- As you went conquering, you just left the borders of former nations/kingdoms/whatever where they were because it was convenient. Countries became provinces.
- Your empire got too big to keep thinking of as one piece, and you had to organize it somehow
- Your empire got so big you started losing chunks of it to invasion or secession, and had to surrender some of your central powers to more regional governors in the name of them being able to defend and maintain the Empire without news having to make it all the way to and from the capital.
- Your empire has been through a few cycles of splitting and rejoining, and the lines it tends to split along just turned into provincial borders along the way because people got used to thinking of those as borders.
All of these things can impact the size and even shape and organization of your territories.
How independently powerful is a given province?
This is a case study on California and Texas...when these two states joined the US, they dictated where their borders were and everyone else just had to deal with it. At the time of their joining, California and Texas were both already so financially and politically powerful that they kinda got to do whatever they wanted--and the rest of the US knew that those states could just secede if they didn't get their way.
In a more traditional empire, this might be a militarily or economically powerful nation that agreed to join the Empire and were allowed to keep (or even expand!) their borders in the name of a peaceful union. This could also be influenced by having two large and powerful cities, and neither one of them wants to be ruled by the other...so you draw your territorial boundaries to give each of them their own little block and let each rule themselves.
Did you ever notice that a block of the Western states in the US are roughly the same size? That's Thomas Jefferson's fault, he thought that new states ought to be admitted with roughly similar dimensions based on longitude and latitude. While his original proposal didn't go through, the idea got carried out later on.
Did you notice there seems to be a 'stripe' of state borders across the US running from Arizona to North Carolina? That's slavery's fault--The Missouri Compromise allowed slavery in states with northern borders below 36 degrees, 30 minutes north latitude, with the exception of Missouri. So it created a trend of state boundaries forming along that line that persisted even after the Civil War.
And the Virginia/West Virginia split? US Civil War--the eastern block of Virginia wanted secession, the western block didn't...so the state cracked in half.
And, of course, going back to Diocletian, he redrew the Imperial map because he thought it was a good idea and he was the Emperor.
So, you could have political weirdness happening in your empire as well.
Have your provinces gone to war with each other lately?
Yeah, that happens. It is far from unheard of for the ruler of one province to decide they want the land of another province and to invade. So your provinces might be different in size because they conquered additional provinces (or chunks of another) and rolled them in. This is most common in a more feudal or confederate structure where the provinces have a lot of self-contained power (particularly, they control their own military forces)
Final consideration: How long has it been since the province was formed?
See all the above notes? Unless someone comes back later and redistricts the empire, those rules apply when the province was created. There's a political inertia to territorial boundaries and just because a province made sense 200 years ago doesn't mean it makes sense now--but the province has been around too long and nobody really even thinks about changing it. Or if they do, they can't get any momentum.
Practically speaking, you may subdivide your provinces into sub-sections (like counties or electoral regions) to compensate for this.
So very many things to into determining the size and shape of territories that, honestly? You can get away with just about anything. But if you need some historical context, there you have it.