This will continue to be a challenge because humans are simply not great at estimating. I have had success by explaining to managers that a big part of my job is to help them manage risk. In order for me to do that properly I typically need more information than is initially present so that I can give a high confidence estimate. I might say something like, "I can give you a low confidence ball park estimate right now but if you give me a few hours to research then I can greatly increase the confidence level."

After all, you know the least about a project at the beginning therefore no one should have a high degree of confidence in estimates given then.