Which of the following should I go with for a new startup that is just getting off the ground?
My company is a small SaaS application but I need full root access to a server in order to be able to setup it up properly.
Digital Ocean and Heroku do not offer the same type of service.
Heroku doesn't offer root - but in some cases, that may not be important if the platform you select matches the provider (Rails, for example).
A VPS (Digital Ocean) provides root to an instance, as does EC2. The difference is that with Amazon, a VPS is a component inside the Infrastructure as a Service (IaaS) offering. Additional offerings like private networks, various storage options, message queues, database instances, and map-reduce services allows you to grow beyond a simple cluster of VPS'es.
That said, many times startups just need to get things going and NOT do premature scaling exercises. This is why many chose VPS'es to start, then one customer-product fit is achieved, re-evaluate their platform and redesign at that point.
VPS vs dedicated server or colocation is a decision that typically occurs when the demands on a VPS are close to exceeding capacity offerings OR the cost per instance approaches the cost of a dedicated box.