One of the lessons I learned early in my career was from the Mythical Man-Month, about building a pilot system. It's often paraphrased as "you're going to throw the first one away".

I think this is the bridge between waterfall and agile that deserves more attention. Use agile methodologies to build a prototype (or multiple small prototypes). Figure out what works, what doesn't work, and what you'd do differently if you were starting from scratch.

And then start from scratch.

With the experience you've obtained you'll know what you're building, and have your waterfall specs.

I would argue that the second rule is even optional here. There is enough literature (McConnell's Software Estimation, Boehm's Software Engineering Economics) that suggests that, given a well-scoped problem and other projects to base the estimation on, a good (+/-50% or so) estimate is possible. But if you don't know what you're building it's all wasted effort because you're estimating the wrong thing!