Em primeiro lugar, não tenho conhecimentos profundos em infra, o que escrevo aqui foi a experiencia que tive em alguns testes de um projeto pessoal.
Se você não quer ter “surpresa” quanto a preço inicialmente, recomendo procurar alguma solução de hospedagem compartilhada com preço fixo e com regras claras. Digo surpresa, pois serviços de cloud tem diversos pontos de cobrança que vem como adicionais exemplo armazenamento, trafego, segurança, gateway, banco etc.
Tem 2 sites que gosto de utilizar para este começo que já vem com Banco de dados MySQL, gerenciador CPanel, SSL, e-mail, muito fácil de publicar por ftp ou ssh e o preço fechado por mês é muito barato.
Para Java Spring que é seu caso utilize o integrator.com.br.
Se for rodar uma aplicação PHP recomendo o hostgator.com.br.
Caso sua aplicação comece a crescer (estou torcendo aqui), você pode optar por pegar um servidor dedicado dentro destas plataformas, ou migrar para um serviço de cloud de sua confiança.
Abs.