I’d start answering this question by asking “why do you want to leave heroku”.
If as you’re stating, the recent security issues are the main reason, I am pretty sure you’re not going to find a better solution by switching. Any vendor or internal ops team is going to have vulnerabilities. Thinking security issues are limited to Heroku is not logical.
However you might object to the way they handled the security issues. I totally agree with that being a good reason, not because of this specific incident, but because in my opinion, this is a sign of bigger issues at heroku. In short Heroku has been stale from a product point of view and has lost a lot of good talent to deal with product and operational needs they have.
To me, replacing one PaaS with another is not a good idea. All PaaS providers suffer from the same fundamental issues of rigidity (you work around their limitations and not the other way around), price (they can’t transfer commoditisation of the cloud to their customers), and vendor risk (single vendor that can be bought and shut down by the buyer - remember AppFog or Tutum? - or at least lock you in)
Doing it yourself is also not a very wise choice for a lot of people: you either need a devops and SRE team or you’re left copy pasting scripts from across the internet to build and configure your servers.
Alternatively you’re pressed to learn a new tech (kubernetes, dokku, et al) and spend your time on that instead of your app.
I’m a proponent of a middle ground: vendors that take care of devops for you, the way your team would have done so, without the inhibitive costs. Consultancies are one option but they can build something for you at a cost and then you’re left with either keeping them around to maintain it to stuck with a tech stack you can’t manipulate yourself.
Companies like Cloud 66 or any other ones that build and maintain a PaaS like experience on your own servers without their own complex magic are the best ones out there in my opinion.
I’m biased towards Cloud 66 as a founder, but we built it not to build another PaaS, but to try to address the actual question of why everyone starts with heroku and no one seems to stay on it for long.