I've had games where it took me 10-20 years to find a habitable world. Then on my current game my very first system I jumped into to explore had a colony cost 0 planet; the second system had a world that with a little bit of terraforming was habitable. In fact in my current game I have 8 warp points from home system and, with terraforming, 5 of those systems have a habitable world.
What WILL take a long time is getting a world up to self-sufficiency. The first colony in this game was in a system with few minerals. The second colony was on a world overflowing with them, with decent accessibility. It's taken me 40 game years to get this world to 400+ factories, about 600 mines, and a bunch of ordinance factories and refineries. In the last 5 years or so they started building ships (because I towed in a couple of shipyards). At times it seems like I've let all the other colonies go to bootstrap this one. And I keep finding systems with habitable worlds...