Actually, terraforming doesn't take that long. It's measured in years, sure - but most things are.
I have a fleet of twenty 5 module terraformers and have fully terraformed everything in the Sol system except Venus (Mercury, Mars, Callisto, Titan) at year 2040 (so 15 years into the game). I haven't bothered to expand outside Sol yet, though - I've explored a few systems, but so far almost every system has been mostly empty (one had those star swarm things, which I'm leaving alone for now). Not a single world large enough to have even the measly 0.2 gravity that I need to live on. Well, except for a couple in the swarm system - but I'm going to research better missile tech before I go after them.
I had Mars done really early, you only need to add a little bit of gas to make it a 0 cost planet. Just .1 oxygen and about .19 or so "safe greenhouse gas." Mercury only requires about .6 or so anti greenhouse gas as well as the oxygen. Callisto is a bit tougher, requiring about 1.1 atmospheres of safe greenhouse gas, the .1 oxygen, and I think you have to remove Methane (or was that Titan? I can't remember) - plus you can only live on it with very high gravity tolerance, the game generation gave me 80 this game and I didn't bother changing it. Titan can never get to 0 with 22 temperature tolerance, but you can drop it to 2.0 and get your civilian sector (if you have one) to deliver all the infrastructure you need just by delivering a few colonists and letting the freighters haul in civilian owned infrastructure for free.
It's really great to have all these colonies right by eachother. I only have 5 freighters, but they deliver stuff within a few days due to the short distances. Mercury started with a bunch of minerals, including the stuff to build financial centers, so I'm building it up as a super finance base. Mars was empty, so I'm just shipping in research labs and using it as a big research base. Callisto had Uridium and was lacking the Corbomite, but a bunch of commercial mines popped up with Corbomite so I have them all sending it to Callisto via mass driver and am building it as a commercial base too. Titan is still small, but I'm building a large mining base there via construction factories hauled in, since it has a huge deposit of Vendarite (the only thing Venus is lacking). The money is flowing in and I'm researching at an incredible rate. Venus has over 100 million minerals in 10 types, which are going to Earth via mass driver and supplying my construction efforts - supplemented by Titan's minerals.
I might have been lucky with mineral generation, but so far I haven't even been bothered by the fact that I can't find any decent colonies outside the home system.