You should first think of which problems you want to solve with your high availability setup. What concerns you most: an outage of your webserver, an outage of the data center or an outage of a large internet link/country blocking for example. Do you want to protect yourself against bankruptcy or malicious acts of the hosting company? Expensive hosting facilities are not immune to data center outages. Maybe good to know that on average two data centers per year suffer severe hard disk damage and outages due to errors while testing the inert gas fire suppression system. An ING Bank data center was knocked off-line for ten hours by this for example in 2016. In 2007 a truck driver in Texas hit a transformer near a Rackspace data center causing an outage of 36 hours.

So first of all, plan the locations of your servers wisely.

Every problem puts different constraints on your setup. With currently nine dedicated servers in the field and a high availability setup, my experience is that not the server hardware, but the hosting company/data center is the most common cause of problems. And the second largest cause of availability problems is the server administrator, aka myself. In the last few years I had only one server failure due to hardware problems, but much more outages due to actions like the replacement of central routers in the data center upgrades of server rooms/racks etc. or hickups due to software upgrades.

The core of my high availability setup uses five dedicated servers leased at three hosting companies in three different countries. That pretty much protects me against problems on a data center level, or disputes with the hosting company (ran into the latter problem one time)

Then you want to reduce all single points of failure. A single firewall should be avoided, as well as a single HA-proxy server. Also a self-managed DNS server is a single point of failure. If your sites are dynamic and use a central database, that database server is another point of concern. Eliminate these as much as you can. Database servers can run in clusters, as can ha-proxy but it needs planning and technical knowledge to do it right.

Round-robin DNS as you mentioned does not check which of the servers is up, and will assign IP addresses at random to clients. I.e. if you have two servers with two IP addresses and one of your servers fails, 50% of the clients will be handed out a not functioning IP address. I don't think that is your definition of high availiability, so you shoud look in other ways to deal with it. I use a DNS service provider with a distributed network of DNS servers which automatically checks the availability of a server with an HTTP request every minute. This HTTP request calls a small script which checks the database state and server functionality. If everything is fine, an OK message is returned. Otherwise the script returns an error message. Any other respons than OK is interpreted by the DNS server that that particular server is off-line, and as long as that is the case, that IP address is not handed out to clients. The TTL is set to a fairly low value of 300 seconds, causing clients which are connected to a failing server to reconnect to another server in the cluster after a maximum of 300 seconds. For the purpose of this system, that is good enough.

Thanks for such a complete and well though out reply. I very much appreciate it.

"I use a DNS service provider with a distributed network of DNS servers which automatically checks the availability of a server with an HTTP request every minute."

I think this is what would serve me best. Can you recommend your provider or point me in the right direction? If you don't want to post it publicly, please send me a PM. Thanks.