I like EnjoyVPS: http://www.enjoyvps.com/unmanaged-linux-openvz-vps/
I've deployed a small Grails app using the 512MB plan which is only $10/month but you might want the 1GB option for $20/month. It's not as simple as EC2 but pretty really not bad at all. Just pick a distro (for limited ram it's best to go with a 32-bit OS), unpack Tomcat to /usr/local and deploy your Grails war to /usr/local/tomcat/webapps.
You could try Google App Engine - free for even pretty big apps, restricted by various quotas.
By detault the app is available through your-app.appspot.com and it looks like you need to use Google Apps to point your own domain name at the instance. The standard version of that seems to be free now, though.
GAE gives you a data store which is accessed through JDO or JPA, so you won't be using Hibernate over a relational database. For that and other reasons it needs a plugin to get Grails running: http://www.grails.org/plugin/app-engine
Persistence behaves slightly differently to the standard Grails/Hibernate stack, so that may not suit you - have a look at the plugin documenation.
I managed to deploy a Grails application in a VPS with 512MB of memory but that was quite precarious and failed from time to time. Now I´m in a dedicated server account with 1G and works perfectly. I just use Tomcat as web server