Personally, I think an extra pregame setting (like the income rate and culture spread settings) that modifies titan construction rates would be the best way to go.
There is such a setting called build speed already, and it affects all construction rates. But I agree, I think titans need to take longer to build, require at least 5 labs, and perhaps not get so powerful when leveling up.