You could always push back their deployment by changing the titan factory from using tactical slots to logistics slots. As it is currently you can whack the factory pretty much anywhere. Having it take up logistics slots would make it more of a choice, as you'd be possibly sacrificing trade ports/labs, and it would also make it take slightly longer to get a titan as you'd need more planets for the logistical slots to get enough labs for the titan research.
I'd also like to throw my vote in for them taking longer to build, and having the research be more expensive, as they are currently far more powerful and cost effective than any alternatives when looking at how long they take to build/how much they cost, and a longer build time would let a player that went for the capital ships/frigates have a chance at rushing and destroying the titan factory before said titan was built and proceeded to stomp their fleet into the ground.
Note that I don't think titans should be more cost effective than a comparable fleet, as you only get one and they should be sufficiently bad-ass, but I feel that in their current state they are just too much better then any alternatives.
When someone starts building a titan you should be thinking that it's imperative that you stop it (Almost impossible to do atm considering how quickly they can be built, and how difficult you can make it for any early fleets by so much as planting a starbase or defences on the planet) or better be on your way to your own titan, as it creates an interesting change of pace in the game. But having them pop up all over the place in the first 15 minutes of the game greatly lessens this, as you have fewer resources with which to oppose them, and it just becomes "mundane", especially when (as in their current state) it is a far better idea to just rush a titan and start levelling it, rather than developing your fleet/empire or focusing on smaller skirmishes and territory control.
Esentially, I feel it should go
Early game (Skirmishes with small fleets, quick territory grabs)>Mid game (Starbases start going up, change in ownership of territory is slower, more marked terrtory borders)>Titans>End game (Large fleet/titan conflict, starbase assaults etc)
Minimum expansion required for 4 military labs>Titan research>Titan>Fleet(for support)/Starbases>End game (Titans plus supporting fleet versus other titans/supporting fleets with starbases sometimes thrown in)
As far as having the titan take longer to build/be more expensive is concerned, it's not so much about the fact that you could still build a titan early as it is that people that went for a more fleet oriented approach would have more time to build up enough to properly oppose a titan, ie it's not removing the fact that some players can still rush for a titan, it's just making it a more even fight between titan rushers and those that focus on fleet and empire tech, so adding viable options other then titan rushing.