|Yes, you will want to go with a higher end VPN that supports IP Security (IPsec) which will encrypt the data before it is passed through the internet. |
As for how to setup the network you will need a way to get the decryption key to the clients securely. I suggest you setup a certificate server for this. You will need someone who knows Cisco (Maybe Cisco Certified) and has an understanding of how to setup VPN networks.
There is nothing wrong with third party as long as you do your home work. Research the company and ask to see if you can have a tour of their facility. See if they have physical security to protect the server that your data is going to reside on. The advantage to third party is they set every thing up for you and you have off site backups so if your office burns down your data is still safe. The disadvantage is they are expensive and if you need support on the servers that your data resides on, it can be slow.
So like Wanderer said we need to know a little about how your data is accessed. How much does it cost you to be down, what kind of systems will be accessing this data and so on? As suggested above, I would get a consulting company to come in and put together a plan for you. They will audit your computers to see what software you are using and the needs are for these systems and give you suggestions.
I would say that with 20-30 people accessing the data remotely is not a lot but it could all depend on how fast the connection is to the internet both on your end and theirs. Another question that has not been asked yet (I don't think) is do you have any remote offices that will be tying in? If so you may need to equip them with VPN routers to establish a Point to Point VPN that is always on.
"external storage device"
If you do is this device going to be used for backups or live data? There are couple types of external storage devices Network Accessible Storage (NAS) and Storage Area Network (SANs) and each has pros and cons. We would need to know a little more about what you are planning to do to make a recommendation.
As stated above you really will want to bring in a consultant but we can at least help you with what kinds of questions you should ask.