I would strongly recommend against EC2 for your first foray into dedicated hosts. EC2 has very specific applications, and there's a much steeper learning curve involved.
At this point, there are coarsely three directions to go, and pros and cons for each:
Managed dedicated hosting: I've never shopped for managed hosting firsthand, although I've interacted with it in the past when working for clients who have pre-existing sites. In the higher-service levels of managed hosting, you'll have a salesperson guide you through the entire process including purchase, migration, and so on. Associated bills run around $500-2000 per month in my experience. Managed hosting may be the best choice if you don't want to be a generalist, don't have a partner on whom you can pawn the server management role, and have a large hosting budget/requirements.
Unmanaged "assisted" dedicated hosting: MediaTemple is the name that pops up most prominently in my mind for this. I have used MediaTemple extensively, and their services were the first ones I used after "graduating" from shared hosting. Their dedicated hosting package is unmanaged in the sense that they won't set up your load balancing, DNS, migrations, backups, and so on. Nevertheless, they have a nice control panel for system tasks, and a whole bunch of software comes pre-installed like Plesk, which in turn manages/implements pretty much the "all you'll ever need" stack including Apache, PHP, mail, monitoring, MySQL, and so on. I have managed fairly large sites on this not having to touch the command line more than once or twice. Another plug for MediaTemple is taht they also have quite good telephone support, at least when I used them. Unlike shared hosting, where support is (understandably) non-existed, even when I was on their cheaper plans, there was always someone to pick up the phone 24/7 who was quite knowledgeable. Unmanaged "assisted" hosting is probably your best choice overall. You can manage this yourself with limited difficulty. It's a hell of a lot more affordable than the managed solution (roughly 50-75% savings, hardware for hardware). A the end of the day, most such hosting providers do give you full access to your system in the manner of a full-fledged VPS, so you probably won't be constrained on what you can do.
VPS: Finally, you can go with the almost completely unmanaged VPS route. Linode is a big name here and what I currently use. Slicehost is also a big name, although comparisons generally have it coming up short (its prices for each VPS size are also less competitive). Another name floating around these days is prgmr for the more 1337 among us. Prgmr offers the best prices, (allegedly) the best performance, and the most customizability at the low levels. In any of these, you'll essentially be put on a basic installation of a Linux distribution with some of the other stuff sorted out for your (DNS records, IP addresses, intranet, some router/firewall-level protections against, for instance, DDoS). Beyond that, the instructions are basically just "go". Slicehost and Linode both offer quite extensive guides to do almost all basic tasks like install the LAMP stack or maintain your system. For me, a huge benefit was being able to move stuff, test, and deploy across multiple developments in an instant is the biggest plus. Before, I had to FTP lots of files, manually run queries in the lovely world of phpmyadmin, set up site-by-site deployment scripts, and deal with cross-system messes all the time. Now, I can just have everything hooked up together! Finally, with the VPS, I know what's going on on my server, and I can do anything to it. One of my first steps was to install a private Git "server", but you could just as easily set up a VPN, an SSH tunnel, or a distributed programming project node. *The VPS solution is by far the most work for you in terms of actually touching the system administration. However, it is the most customizable, which just may save you work at the end of the day (isn't that the goal). *
