I have a good experience with cloudsigma.ch (but that only replaces the EC2 part, so it depends on what you need).