i figured my first step was to carefully plan all the pages and how the menu would look.
Then i would do my master page for the menu and nav controls.
Yes, that makes sense to me. By planning what pages you need you can make up the structure and functionality of the site. This helps in planning the menu and navigation system. Then the master page comes in as you need one before you create the actual pages that are based on that master.
However, IMO, you don't have to do things in a strict order. It's a process of constant refinement where you can add pages to the navigation system later, make changes to the master page that affect all pages and so on.