The blockchain will be the most expensive part of you cost if going the VPS route; disk usage will only increase where as RAM & CPU stats will stay ruffly the same. I'd shoot for ruffly 100-120gigs of disk space available so that your hosting costs don't change for a while; makes keeping the books in order a bit easier. Also look for hosting providers that state they don't limit/cap network usage and hosting providers that support loading your own kernels. This last suggestion is because after reading the previously written comments it's obvious that you'll use a VPS regardless of warnings and you'll want to minimize attack surface from the Kernel level on up to file system and beyond.
As far as suggestions of VPS service provider, supposedly Digital Ocean supports custom kernels if you submit a support ticket. They also don't cap network data usage last I checked. While I may not be using them right now I've tried their service and my experiences with them was good. Most issues/questions I had where answered (or at the very least recognized by staff if it was going to be a bit to get back to me) within the a business day or two.
Last point on security for your VPS, ya may want to check into grsecurity kernel patch and how to merge it's features into the kernel of your choice. It's tough to setup but very much worth it to have some protection at the very lowest levels accessible on your remote server.
Edits/updates
So after a little messing round at the terminal I found the following scriptlet maybe helpful in notifying you when space limitations are nearing the time of upgrading vpn storage.
#!/usr/env/bin bash
Var_mount="/media/btc_node"
Var_max_percent="80"
Var_current_present="$(df -H | grep "$Var_mount}" | awk '{print $5}')"
if [ "${Var_current_present//%/}" -gt "${Var_max_percent}" ]; then
# put stuff to warn ya like mail here
echo "# Critical space levels on ${Var_mount} ${Var_current_present}"
fi
The above could be further modified and added to cron to occasionally check and warn you of when upgrade to space will be needed.