Starting a fantasy RP is... hard
The way I do world-building is neither to start large nor small, but both, and work in from both ends toward the middle.
You need some sort of overview of your world, or universe, how it works, how you move around it, who the people are, races, species, gods if you need them. Basically just describe your setting on one side of A4. It's just a framework.
Then go to the other end. What do you want this particular adventure to be about? A dungeon crawl? Then all you need to do is lay out the dungeon and its contents. Nothing exists beyond a framework until it is brought into being by action.
If your game is to start with the PCs in a nearby tavern, then make a sentence or two describing the bar room. It's just a facade, a stage set, and you're a set designer. You don't need to describe or design the layout of the entire tavern, how many bedrooms it has, where the connecting doors and stairs are, because the PCs/audience will never go there. The bar room is just a scene.
Likewise the village the tavern is in - unless the PCs are going to have a battle there, you don't need it. In fact you don't need to describe up front whether the 'floating' bar room is in a village, or at an isolated crossroads on the moors, or in the hold of a vast starship - unless it becomes pertinent to the plot. The plot is about the characters meeting in a bar room and then finding a dungeon. All you need to build/describe is the bar room and the dungeon. The rest doesn't matter.
So what happens when the PCs inevitably go 'off piste'? I hear you say. That's when you use your overview knowledge of the universe. You will have a handle on what sort of things may lie beyond the immediate scene, and you will also have a handle on what you want to do to with players who go off piste. Do you want to reward them or punish them?
You will already have a hazy idea of what might be nearby, and a hazy idea is all you need. You bring them into being as they are needed, like a cartoon character laying railway line in front of his train. You know where you want the PCs' train to go, or where they want it to go (and if you don't, ask them OOC), so lay track in that direction.
What you develop at a local level might give you some further insight into the universe at large. If so, write it down for use later. If all of your games take place in the same universe, it will grow and take form over time - you just have to make sure it remains consistent.
Repeat as required.
There is an exception to this - the GM as an artist, which swordchucks mentioned above. If you enjoy your world building and it's a hobby in itself, then by all means go to town on it and reveal some of its rich splendour to your players as they go. But don't expect any accolades. Most of it you'll never use, and even the bits you do use will never be appreciated by the players, because they'll never see the effort that went into it. You're doing it for yourself, nobody else.
Sometimes you can start out with a facade universe, get the bug, and turn it into a detailed work of art. If you're enjoying what you do, it doesn't matter how you do it. If you're not enjoying yourself, stop. :)