What is the best way to secure remote server/tool access from many locations?

I have a number of remote servers I lock down by restricting SSH to specific IPs. Equally, our internal customer admin tools are also locked down by IP. This is fine when working from the office but if I am at a different location (perhaps on public wifi) or on my iPhone, the IPs will be changing.

What is the best way to set up remote access so that access can be allowed from any location but still maintaining security?

My answer would be to set up a VPN to tunnel all connections through and only allow the VPN IP access. If this is the route to go down, I do not want the VPN located in the office but would rather have it remotely managed. Are there any VPN-as-a-service providers?

What about having one box that doesn't have IP restrictions or loose restrictions where you can SSH into and from there into the other servers? Even a small computer (even a Mac Mini) would work and this box can sit in a data center for only this purpose. A computer that doesn't cost extra power and might be useful for other things (such as surfing the net while at the data center--if the other boxes don't have a gui). The chances of this box going down are slim because it's not doing anything else (make sure sleep is off :) and if it does, it probably means the data center has...well, had a fire.

Hamachi is the only managed VPN service that I'm aware of- but it won't work with an Iphone.

I'd suggest using locked-down IP addresses as well as a port-knocking implementation that starts an SSH daemon running on a non-standard port, configured for non-standard access.