How do you make a good choice of server host to run an exchange on? I was looking at Amazon Web Services recently but they are based in the US - maybe not a good idea following what happened with mtgox.

I then looked at Linode as they have a pretty solid reputation, but I am concerned with the security issues they have had (bitcoinica lost all their funds because someone hacked the actual Linode admin panel, and I am still seeing security issues on their news in 2013).

I have what I think is a novel idea for an exchange and want to try and get a toy hobby project up and running... but how do you choose a server with good ram so it handle a surge in traffic? The ones I listed above are examples of what I don't want.
First of all, don't even consider using VPSes for these things. As long as there's a layer above the OS that can be hacked, the data cannot be safe.

Also, if things are going to be safe, you're going to need at least several machines. The machine that stores the bitcoin wallet information shouldn't be connected directly to the internet, and should not run on the machine that also handles the website.

As long as your server is an actual physical server at a company you can trust, you should be fine hardware-wise, as long as you don't run out of resources.

Of course, software is a far more important factor here. VPSes should be considered untrusted, as there's software running on the machine that you cannot control. As I already mentioned, don't run the webserver on the same machine where the wallets are stored, because a programming error can probably allow attackers to access those wallets.

Don't assume that network traffic between your servers is safe: a routing error or packet interception can cause a lot of trouble for you. Always encrypt traffic between the machines.

Don't trust closed-source software, and don't use beta quality software. They tend to contain more bug than open source software used by lots of people.

Always assume that your own code sucks. This is a very important part. Even if you're an extremely good software developer who has ten years of experience with security, you're going to make mistakes in your code. These things can be code injections that allow attackers to steal password, exploits that allow attackers to view the source code, etc.

But the most important part is that if you read this answer and learn new things about security, you shouldn't be starting a bitcoin exchange. You are dealing with people's money here, and if this answer taught you anything new, you definitely don't know enough about security to start a bitcoin exchange.