The main thing you’re looking to do is to pass the WebTrust audit and associated practices that the platforms will require you to do. Microsoft has the most mature process. They have a set of rules and guidelines. If you follow them, you’re in. One of those, by the way, is that you have to be a retail CA, as opposed to an internal one or a government one. It’s best to work with Microsoft first, and once you’re in their root program move to the others. They are fair, disciplined, and helpful. Most of all, once you’ve gone through all that, it’s easier to get into the other important root stores.
This is an interesting description of the process Jon Callas drove at PGP to get them into the CA business. It’s instructive to understand the process, especially since compromising a CA seems to be the path of least resistance for a bunch of attackers to execute on multi-faceted attacks. I think it bears mentioning that starting the CA is really only the first step. Having certs in any of the major browsers makes you a major attack target. So even if it costs $250K to get things up and running, it will cost a lot more over time to protect the integrity of your CA.