First, 512MB is just a bit too little to run Solr 3.6 with Tomcat, Solr 4.0 may crash.
I Used to run Solr 4.0 on EC2 micro, it has 613 MB ram. it was not enough to run a small Solr site (5-10 req/s)
To Run Solr safely, you will need the 1GB linode. But I do recommend a 2GB machine to run SOLR smoothly.
On my 1.6GB SMall EC2 Server, I set SOLR max memory to 1.2GB, and leave the remaining 400MB for OS caching and other small services like monit, munin, ssh, apt-get, rsync, backups, etc.
this is my JAVA_OPTS that I set on my .bashrc file:
export JAVA_OPTS="$JAVA_OPTS -Xms1200m -Xmx1200m -server -d64 -XX:MaxPermSize=200m"
export JAVA_OPTS="$JAVA_OPTS -Djava.awt.headless=true"
export JAVA_OPTS="$JAVA_OPTS -Dsolr.solr.home=/mnt/Solr/Home"
Amazon EC2 CPU is very low compared to Linode, but I have great performance with it since Solr uses almost no CPU but a lot of ram...
you could go with EC2 medium for a large Solr Server.
PS. Also I noticed your Screenshot that you have the kswapd0 process that recorded a lot of CPU IO time. I have that issue with linode and it was because of an outdated kernel. you should reboot your maching with a newer kernel.