Your reason for not wanting to use EBS is that it is slow. You may want to test EBS optimized instances plus Provisioned IOPS EBS volumes (which can even be RAIDed for higher IOPS). This will simplify making data available to new instances.
Note that an EBS volume takes a while to make all the data available at highest performance. I.e., the performance you get on a fresh EBS volume is slower than the performance after the volume blocks have been populated.
Here's an article I wrote which talks about this process, including one way to identify when an EBS volume has completed initialization from a snapshot (though it basically includes transferring the entire volume through the network anyways):
http://alestic.com/2010/03/ebs-volume-initialization-from-snapshot
If your application wants to start right away at the expense of being a bit slow when it needs to access previously unread data, then I would recommend EBS optimized instances plus Provisioned IOPS EBS volumes, possibly in RAID-0. Once the volume(s) populate, the application speed should ramp up considerably.
Otherwise, the name of the game when loading data from S3 is parallelization. You can have a hundred concurrent connections downloading pieces of the data from the super-scalable S3 service, as long as you are using an instance type with sufficiently high IO.
Even on a 1Gbps interface, however, it will still take over an hour to download 500GB.
Here's a possible trick to consider: With an EBS optimized instance you get a dedicated network interface for the EBS subsystem, separate from the standard network interface. You might be able to cut your data load time in half if you download half the data from S3 and the other half from an EBS volume.
Just in case you hadn't considered it: Make sure your data is compressed in storage to reduce transmission time.
