We've been using Watchguard linux appliances for a couple years for firewalls and VPN tunnels. The price/performance is solid. They have a range of devices that I think would fit your needs.

We have a few Firebox IIIs, medium duty, rackmount firewalls, and twentyish of the SOHO 6tcs - lighter duty, smaller firewalls which max out at 50 trusted IP address and 10 concurrent user VPN tunnels. Currently, we use the SOHOs in our smaller offices (typically up to 30 users) to create a tunnel back to our corporate office.

They have a good user interface and provide good (albeit subscription) support and overnight replacements as needed. The Firebox came with 1 year of the subscription support; SOHOs with 3 months.

In my experience, the Fireboxes almost never need a reboot. The SOHOs need a reboot every once in a while, but usually reboot themselves when needed.

-jk