He pasado por 4 empresas distintas de hosting compartido con soporte para Tomcat (private JVM, shared JVM, heap size ampliado, etc) y todas, antes o después me daban problemas por el alto consumo de memoria de tomcat.
Si puedes permitírtelo te recomiendo un vps con Linode (
http://www.linode.com), o al menos un vps de esos económicos (15 dólares al mes sin administrar).
También depende de para qué sea la aplicación. Si va a ser una aplicación enfocado a clientes un vps. Si está en fase de desarrollo podrías empezar con un hosting compartido pero ten en cuenta que no tendrás acceso directo al log del tomcat ni podrás configurarlo a tu gusto, algo que puede llegar a ser muy importante para tu aplicación.