Been thru 2 vps servers already... 1and1 and PumaHost. 1and1 couldn't get smtp sending to work. Pumahost has awesome power and price... but they and I cannot figure out bounce imap error (yes I have the 5.3 cli php extension installed with 5.4php regular web version).
Vultr for the win.
If you must have CPanel, pick one of the supported CPanel distros (ex. CentOS 7 x64).
Pick the $10/month instance as a minimum.
Buy your own CPanel VPS license from BuyCPanel for $14.95/month. (They buy licenses in bulk as the regular price at CPanel main is $20/month.)