Jeff, eu discordo, balanceamento de carga não implica redundância, é exatamente o oposto de fato. Quanto mais servidores você tiver, maior a probabilidade de você ter uma falha em um determinado instante. É por isso que a redundância é obrigatória ao fazer balanceamento de carga, mas infelizmente há muitas soluções que fornecem apenas balanceamento de carga sem realizar nenhuma verificação de integridade, resultando em um serviço menos confiável.
A roundrobina do DNS é excelente para aumentar a capacidade, distribuindo a carga em vários pontos (potencialmente distribuídos geograficamente). Mas não fornece failover. Você deve primeiro descrever o tipo de falha que você está tentando cobrir. Uma falha do servidor deve ser coberta localmente usando um mecanismo de controle de endereço IP padrão (VRRP, CARP, ...). Uma falha de switch é coberta por links resilientes no servidor para dois switches. Uma falha no link WAN pode ser coberta por uma configuração multi-link entre você e seu provedor, usando um protocolo de roteamento ou uma solução layer2 (por exemplo: PPP multi-link). Uma falha no site deve ser coberta pelo BGP: seus endereços IP são replicados em vários sites e você os anuncia à rede somente onde eles estiverem disponíveis.
Da sua pergunta, parece que você só precisa fornecer uma solução de failover do servidor, que é a solução mais fácil, pois não envolve nenhum hardware nem contrato com qualquer ISP. Você só precisa configurar o software apropriado em seu servidor para isso, e é de longe a solução mais barata e confiável.
Você perguntou "e se uma máquina haproxy falhar?". É o mesmo. Todas as pessoas que eu conheço que usam haproxy para balanceamento de carga e alta disponibilidade têm duas máquinas e executam o ucarp, keepalived ou heartbeat para assegurar que uma delas esteja sempre disponível.
Esperando que isso ajude!