EC2: Holy crap a free Tier. I missed that.
Linode: slightly higher end? lol first time i ever heard that. I have used them ages ago. I had problems, the upshot was that i got refunded all my money about 3 months later.
What ever hosting you find. You will need to do a bit of configuration. However it is not that hard.
So on a clean linux (a virtual thing, looks like you own computer but with really low ram and and HDD), all you need is java as you say, just install the JRE. I install my own JRE even if they provide one. Master of my own demise and all that. Typically you want to have an account that is very locked down that you server will run as. Then just run the server from that account. Put it in the background or use something like screen if you want to logging without proper login
That suffices to get you off the ground. But for production with uptime requirements you will need to muck in and get dirty with many more details and how things fall over etc. But at this point just logging back on and checking the logs works fine.
Just be aware that you can burn through your bandwidth and cpu allocations much faster than you think.