Use Linode. Also, don't miss out on their library of HOWTOs, they are quite good.
Did a prelim computation for the EC2 fee equivalent of Linode 360 with 16GB storage and 200GB transfer. Assuming these limits are maxed out, it seems EC2 is more expensive by 10 bucks.