I'm on a VPN right now, and use openVPN.
from the options you listed,i would go with linode, as you're already using them for hosting. if they charge extra for VPN and you're not paranoid you can go the host at home route (if you're really paranoid and assume someone is watching you, they may not know WHAT you're doing but you can assume they know where you are sending it to, and contact your ISP to give them the unencrypted outbound connection packets...)
What I've found is, depending on how far away from the VPN server you are, that latency (not bandwidth, especially in your case) is the weak link in terms of performance.
And test your connection/configuration a few times BEFORE hitting the road, trust me