I would go with a hardware firewall solution. Easy to setup and should sit and collect dust while it works for your client.
You are going to need a router - probably a firewall anyways for each site (as it has Internet access). Might as well get a stateful packet inspection firewall with VPN capability and get it all done in one box.
I strongly prefer appliance based VPN solutions as they are simple and secure. People are also less likely to "play" with an appliance (mostly because they don't have a monitor, keyboard and mouse), where all to often servers get played with or changed which can cause instability to the VPN/Firewall components that are running.
SonicWALL makes robust VPN appliances, I've personally set up over 300 of them and find them to be good for projects where you want to "set and forget" the firewall and VPN components. They are relatively easy to configure and their firewalling is ICSA certified and quite secure (which should make your client happy).
But if your budget is not up to the cost, you could use a product like Netgear to VPN the three offices together. But watch that you don't underpower your routers.
I recommend using AES or 3DES encryption for your VPN. These are among the strongest commercially acceptable encryption standards available today.
Just remember that you should have a different LAN range for each branch - this is very important so you don't confuse your VPN routing.
For example:
Office 1: 192.168.0.x 255.255.255.0
Office 2: 192.168.100.x 255.255.255.0
Office 3: 192.168.200.x 255.255.255.0
Yes, it may be a pain to change a networks IP range, but it's a necessary evil.
By default the Firewall/router/VPN appliance will allow Internet access by each branch, and allow access to each other (between branches) using the VPN tunnels. Using firewall access rules you can better secure inter-branch access if you wish.
Hopefully this helps with your VPN decisions!
Zaf
