So load balancing via DNS records is the easiest way to deal with the problem, at the cost of (potentially) long failover times. What would be the next step to load balance your servers? I know Amazon offers elastic load balancing for their platform, but if I'm not using AWS or don't want to rely on them exclusively, then what would be my best course of action to load balance between 2-3 different VPS?
You should think of load balancing and geographic redundancy as two separate concepts, because they have two different best solutions.
For load balancing, the best solution is to put all of your servers at the same provider, in the same datacenter, and proxy connections through a load balancer. On AWS, you can use ELB. Outside of AWS you can roll your own load balancer using software like haproxy.
For geographic redundancy, DNS round robin is good, but I must emphasize that to do this properly you really need to have a short TTL and an automated monitoring process that removes downed servers from the round robin. If speed of failover concerns you, you can set your TTL really low (like 30 seconds) at the cost of slower DNS lookups. You have to strike the balance that suits you.
You can of course combine these - use DNS for redundancy between geographic locations, and at each location use a loud balancer. Note that each location needs to be able to handle more than its share of the traffic, not only because DNS round robins produce a very unpredictable load distribution, but also so a location doesn't get crushed under the load if another location goes down. Theoretically each location should be able to handle 100% of the traffic, but you can play the odds and skimp a little.
(Note: the very best way to do geographic failover is to get your own portable IP address allocation and an AS number, and use BGP to announce your IP address allocation from your active datacenter. If it goes down, you start announcing from your backup datacenter. However, only big players can afford to do this. For the rest of us, DNS-based failover is as good as it gets.)
