We were in the same situation as you with our startup. Heroku was killing us. Just bite bullet and go to AWS. It's not bad at all.

I did hit a snag with RDS - but found a helpful consultant who helped me for a few hours. He made good money and now we have a guy who can jump in and provide a direction when things get too complicated.

Costs are down dramatically and we are SOC 2 certified now. No regrets.