Basically, if there are multiple IP's behind a hostname, connect a non-blocking socket to each, then do a select/poll/epoll/kqueue on all of them. Then, once at least one returns, immediately close the rest and use the newly established connection.
This has three nice side-effects. First, if one of the hosts is down, it will never be selected, unlike now when there is a 1 in N chance that you'll be stuck waiting for a very long time. Second, you don't need to explicitly check whether the IPv4 vs IPv6 stacks are operational. A connection that is returned to you is the one that works, regardless of the underlying protocol. Third, this provides crude load balancing. Presumably the host that connected the fastest is also the fastest to process your request. The my blog post for some numbers.