Which cloud hosting service would you recommend for startups: PaaS like Heroku and AWS or virtual servers like Digital Ocean and Linode?

For a new startup with limited funds and a single developer, would you recommend PaaS platforms like Heroku or self-managed server instances like Digital Ocean?

Also, is it just me or does AWS seems like it has a steep learning curve to get up and running?

I can't provide a clear-cut recommendation, but I can say this -

Amazon is renowned for its low prices. If your decision is cost-driven, then you may want to go with that. Last time Heroku is basically running on AWS and providing an extra layer of framework + service. Last I checked, Heroku was extremely expensive.

One more thing to consider - getting started with AWS is easy. True, it is rich with features and capabilities, but 1) you can get started fairly easily and 2) since it's so popular, you can find plenty of resources and people who can help you with that.

The thing you need to ask yourself is what is your budget and how much your own time is worth to you (in learning new features or maintaining your servers by yourself vs. paying someone else to do that).