Heroku
Heroku was one of the first and best Java cloud providers. I believe the use Amazon AWS under-the-covers.
DigitalOcean
DigitalOcean is a cloud VM provider. They can instantly spin up a configured BSDBSD (FreeBSD) or LinuxLinux virtual machine.
Simple pricing. Very cheap to get started, pay by the hour, less than a U.S. penny per hour.
Excellent documentation and many helpful articles including how to install Java on your VM.
They run their own hardware in multiple data centers. Apparently high quality including all flash-based storage.