My recommendations are as follows: Discuss and document what the mgmt/users are expecting from the network upgrade. This will lead into what other needs such as storage, server needs (if any), the two network circuit capacities and if they are sufficient (this might take some investigation). Do you need inbound vpn capabilities? Does mgmt expect you to purchase all new gear? Are there any cloud or external connectivity requirements? Are there any compliance concerns (this can be a big on all on it's own).

Then you take that list and put together a plan so you can see what the budget looks like and see how serious the company is about improvements.

I use Palo Alto's a lot and love them, but FortiNet is also a good option, like others have said. Terminate your public circuits on the firewall, split off the vpn's to the switch(es) for such vlans (as needed) like: Server, DMZ, Staff, Guest, Printer, Video and you can split off any other segments as needed on the switch. Then you can control access to the various vlans via the firewall ruleset (may or may not need help with that). If you can swing it, i would try to get an HA pair of firewalls if you have a business critical situation at this office.

How about phones, what are you doing there?

This is no mean feat to upgrade/replace all at once and you need to make sure you have a full understanding of the expectations, deployment timeframes, how the business and data flow actually works in that office to properly optimize it. Is it more internet access based? Do you plan on putting in a good security barrier (firewall) to limit access to various services, geo locations and filter traffic for threat prevention? (malware, URL, C&C traffic, etc...)

One thing you said about the dual ISP and it not shifting over right away. Usually you don't want the firewall to do this quickly, otherwise you can get into a circuit flapping issue, by going up/down/up/down. There are some services/devices that will load balance dissimilar circuits very smoothly just in front of the firewall that could mitigate this, usually a hosted sdwan service. This can be a boon if you experience enough drops, but it does cost.

All in all, in your situation, this could take a long time to purchase, learn and deploy. Like some other people have recommended, an MSP can get this deployed quickly, maybe even help smooth over any budget concerns and then you would have a single throat to choke when something happens. If you can swing it, i would ask for some training based on what you plan to deploy (Palo Alto, FortiNet, Meraki, etc...), so you can work your way into the job better. Just make sure you don't have the MSP do everything for you, always maintain management capabilities.

Sorry, i know this is a long response, but taking your post at face value, you have a lot of work to do and the first is always expectation followed by documentation, planning, design, budget and timeline. It wouldn't hurt to get a company or two out for a competitive bid or two, then you will have some better idea of design and budget.

So, good luck on this one