find a colocation company who have multiple data centres linked by a dedicated layer 2 connection. they will give you space for a server or VPS on one site and a server or VPS at another with a e.g. 1Mbps cross connect. I would go up the food chain for this i.e. not just a hosting company but a data centre operator or at least a hosting provider that has layer 2 services to another DC. however, if you try to chose two different companies, there may be a charge cabling and routing to the other provider (are you with me?) The larger the company is (hopefully) less likely to go our of business and the will bundle all the networking/cabling costs in cos it is cheaper for them - you are already on their network so no need to do anything. You can then implement the virtual software that allows for HA configs, such as ESXi - I am no expert here - try other forums for a good answer on specific HA and cluster OSs
