Ask HN: How do you handle estimates when there is no spec?

I've gotten back into freelancing over the last 9 months or so, and I've been pleased to find myself getting better projects than I had in the past. That said, I've been running into problems with estimates.

Clients invariably want an estimate for a project before they hire you. But it's impossible to give a good estimate before you go through requirements gathering, writing stories, etc. I'm considering splitting requirements/spec and development into two separate projects, but I thought I'd see how other HN freelancers handle estimation in the face of uncertainty.