The overworld is the first thing you should plan, because it WILL affect how you end up designing the levels. For example, if unlocking a certain level required a really hard secret exit, that secret level should also be of that difficulty. Once the overworld is done, you can begin doing level design, as that is the highest priority. However, an exception is if some ASM gimmick is a main feature of a certain level design, in which case, you better get that done, or you won't be able to continue working on that level's design. However, you can always prepare sublevels in advance, even though they won't be accessible for a while. In fact, the level that I know will take up the most sublevels and might force me to rethink the other levels due to rom space should be the first level that I design.

Remember, the order in which you work on aspects of your hack is not the same as the order of importance of those aspects. The most important aspect of your hack, which is level design, would be the 2nd thing you work on. In some cases, you might want to save Level Design for last, because the other stuff might put restrictions, and some people want to finish the base rom before working on the levels. (So I guess you can also say that the most important thing is the last thing done, since it may require the other components)

Consider worlds first. Say your hack has a nine-level cave world: if you think you can make each level distinct and fun, by all means go for it, but reconsider if you think you'll run out of ideas. Make worlds and levels you want to make. The first world doesn't have to be grass and you don't have to stick to conventional themes. I'm using numerous worlds, each only with 5 levels, so each is distinct and the player has a lot of variety. It's useful to have a general idea of the levels you want within a world ahead of time.

People have differing views, but I'm all for designing levels out of order. If you're especially excited to work on a certain level, you shouldn't wait until later when that inspiration may be gone. You also shouldn't force yourself to make a level you find boring, since the player probably won't enjoy it either. Remember that we mainly do this for fun: if it becomes a chore, it's not working.

As for the overworld, I put it as one of the last priorities. All too often, you may see a level slot and think "okay, I have to make a two-exit ______ level." Better to finish a level how you want it and then require the overworld to adjust accordingly.

Remember that level design should come first. Often, this means you can design levels out of garbage tiles then fill them in with graphics later, or you can avoid inserting music until the level is done, so you can listen to whatever you want when testing.