If for some reason that is even too much take a look at the top providers on the Low End Talk Wiki here: http://www.lowendtalk.com/wiki/top-providers

Then keep an eye on Low End Box here: http://www.lowendbox.com

When one of those providers runs a deal then get it. If you don't want to have to shop deals then DigitalOcean is a good idea. I have trust issues with Linode so I can't recommend them anymore, and frankly, some of their guides are terrible.

You should be reading the documentation of the software as provided by the vendor of the software along with the docs of your distribution before you attempt any guide because quite often the guides will have you do something that won't work, is suboptimal, or just plain wrong. nginx has an entire section of their wiki dedicated to bad configurations from guides on the Internet and what you should be doing instead: http://wiki.nginx.org/Pitfalls

Understanding the full stack and being able to build it from scratch and tweak it gives you a competitive advantage over people who cannot, and that makes you look better to employers.

It depends on what you use EC2 for. The experience I'm talking about isn't "with Linode". The experience is with taking a distribution that has none of the parts of the typical LAMP stack installed and installing and configuring them properly for the solution that you are providing.

Now experience with EC2 in provisioning many machines of the same configuration using something like Puppet or Chef is a related but separate thing, and is also good to have, but you have to be able to walk before you can run.