The problem you are asking about was a major concern around 2009-2010. It probably delayed IPv6 adoption by a couple of years. Nobody wanted to go first because they feared their website may appear unstable, and users would move to competing sites without IPv6 support.
Many companies put an effort into resolving the problems. Arguably, the Happy Eyeballs approach, which @HåkanLindqvist linked to was the most significant contribution to getting the problem resolved.
In 2011 there was sufficient confidence that the problem was resolved, that major websites made a coordinated 24-hour test run called World IPv6 Day. The coordinated test run was intended to ensure any users still having a problem would not incorrectly jump to the conclusion, that the problem was with one specific site rather than their own connection.
The results were successful enough, that one year later major websites switched on IPv6 permanently in World IPv6 Launch.
We are close to the tipping point, where the problems caused by NAT will get larger than the problems caused by broken IPv6. At the moment both are small enough, that it is difficult to measure if we have already crossed that tipping point.
My recommendation would be to configure dual-stack DNS records as soon as you have working native dual-stack connectivity. The sooner you start, the longer time you'll have to resolve any issues it may have. You want it to be stable by the time it becomes truly mission-critical.
Don't deploy servers on 6to4 or Teredo addresses, if those had been your only options to get IPv6 on your server I would have recommended switching to a better provider.
However I do recommend configuring 6to4 and Teredo relays directly on your own server if your server has a public IPv4 address. Deploying those relays will give a more reliable connection to your server for clients using either 6to4 or Teredo.
Occasionally there will still be clients with broken IPv6 connectivity. But for the last two years, those clients would experience problems with major sites, so you can expect those to resolve their own problem somehow. They are unlikely to see a problem with your site only.
You do however have to pay attention to the IPv6 connectivity of your own site. Should your site have an outage on the IPv6 connection, you may affect a small number of users with working IPv6 connectivity and a pre-happy-eyeballs browser. Those would see a problem with your site only, but everything else would be working.
Just because IPv6 has fewer users at the time being, it doesn't mean it can safely be deployed with less monitoring than IPv4. If anything, I say you need more monitoring for the IPv6 connectivity because you are more likely to not notice any problems.
