The cloud provider problem is definitely real. I have an idea for a service that requires both IPv4 and IPv6, but Linode and Rackspace were the two I found that both support native IPv6. Otherwise, it's something involving a HE.net tunnel, which I'm not comfortable with for more than experimental use.