Hey, if you want a really good and pain free hosting experience, i would recommend https://forge.laravel.com/. It takes a lot of the hard work out of managing your servers.
As for providers, you've got a good selection to choose from. The main ones being Digital Ocean and AWS. In terms of user experience and ease of use - Digital Ocean gets my vote, plus its cheap. $5p/m for a basic 1 CPU / 1GB RAM server which can handle quite a lot of traffic.
AWS you've got more control over, but with that comes complexity, but there are plenty of guides on how to setup stuff on the net. Last time i checked servers are a bit more expensive too.
Object storage for your files, again you can use Digital Ocean Spaces - $5p/m for 250GB storage or there is AWS S3 which i personally use. S3 you pay for how much you use, but in my experience this next to nothing, again depends on how big your files are and how much bandwidth / traffic you use / get.
Drawback of DO Spaces is that its a flat $5 p/m and i guess you're only really getting the full value for money if you use up the available space each month.
I have some guides over on my blog on how to setup Laravel Forge to work with AWS EC2 if you try forge out and want to use AWS
I've also got a guide on how to configure Laravel to use Digital Ocean Spaces
Hope this helps!