For me, one of the most obvious solutions to doing HA over more than two hosts is Load Balancing, even though the name does not suggest HA.
What kind of LB is most suitable for your use-case really depends on the type of client and app, but the three most common options.
L7 load balancing. You have a proxy that understands the protocol used. There are many such proxies for HTTP. It knows how to check if backend servers are alive as well. And with some it is even easy to deal with incorrect response (500). The proxy keeps list of all servers and a list of servers that are alive and working well. Once request arrives, it forwards it to one of those OK backend servers. (This can work with HTTPS if there is SSL offloading as well.)
L4 load balancing works pretty much the same thing, but instead of looking at each request, it looks at each connection. It does not understand the protocol. So it usually works even if you are using something ephemeral or encrypted like HTTPS.
L3 load balancing takes a hash of source IP address (and maybe port) and based on this hash, forwards the connection to one of the servers. Will work even for stateful UDP protocols.
There are more ways of accomplishing this. But I'd say these are the most basic.
Of course now, you've got another SPOF - the load balancer. But as all three these methods (w/o SSL) are not very resource intensive, it is suitable to have a Acitve/Passive configuration using something like VRRP to do failover in case of problems.
L7 for HTTP can be done by software like Varnish (great caching and LB solution as far as my experience goes), HAProxy, nginx, Apache httpd etc. most webservers/proxies can do this.
For other protocols, you have to use proxy specific for the protocol.
L4 can be done by HAProxy and similar software, or through firewall (though you have to implement the status checking).
L3 is done on router and/or in firewall. You could probably do it with Linux and iptables (IPVS), or some commercial software.