AWS is a giant construction store like Home Depot, where you can find everything. Rackspace is local home improvement shop, with good service, which was doing fine until Home Depot build it's store nearby. Now people have less and less reasons to visit it. Some folks like it for the old times sake, though. DigitalOcean is your buddy who works at "Hammer&Nails Manufacturing Inc.", he can get you nice hammers and nails pretty cheap if you ask him, but not much else.
What are your requirements? I can recommend to you a Toyota Corolla or a F150 pickup truck but without any knowledge what you need there won't be good answers. Some startups are blogs, others combine several third-party APIs and yet others are very data intensive.
(I'm running AWS, Linode, DigitalOcean, bare metal server myself, all depends on what the project needs).
I find digital ocean to be much simpler to use. you spin up a linux box, if you need a second one you can do it almost immediately. AWS is more powerful but much more complicated.
I prefer to put my projects on DO and if they scale too much then I would consider using AWS (hasn't happened yet!). No experience with linode.
https://news.ycombinator.com/item?id=9959750