I assume you use SSL, and these are not made on demand (connection pooling ?) On 'cold start' do you get massive latency ?
What kind of latency is there between client and server ?
What made you choose Heroku and not a specific managed postgresql service ?
Did you try flys postgres service?