I am currently operating systems with two different types of VPN devices that interface with all sorts of different networks, firewalls and workstations. While these are representative of what is available, there are other similar solutions out there from Intel, Checkpoint and numerous other vendors.
Of the two that I use, the most elegant and most expensive is the Cisco VPN3000 VPN concentrator. Models are available that will support up to 5000 users at full wire speeds using 3DES encryption. The client runs on Win95/98 or NT or the VPN unit can be configured to support the IPSEC that is native to Windows2000. Firewall configuration is straightforward and there is a NAT mode that can be configured. Your users can just download a client that you pre-configure and be up and running in a few minutes.
At the other end of the cost spectrum is a Linux-based router running IPSEC that lives on standard PC hardware. I'm currently running one based on a P133 and I haven't been able to saturate it yet. The Cisco was about $40k and this solution was about $40 using scrounged parts and GPL software from the Linux Router Project.
So there is a wide range of choices for you.
paul