Agile for Consultant Development Teams

I'm a consultant (sounds like an admission at the start of a 12-step program). I love the Agile approach to software development but there seems to be a fundamental conundrum I haven't been able to solve -- software project pricing. Seems like my clients want to know, in advance, how much the development of software is going to cost (the nerve of some people!). I just can't see how to get a price together for a project using an approach that essentially leaves out the up-front design effort that is characteristic of the traditional waterfall approach. And the Agile experts with whom I've spoken have no answer to this either.

Now, I don't actually believe that the waterfall approach gives any better or more realistic cost estimate, except perhaps on the most simplistic of projects. If anything, I believe it is a more expensive method that produces a false sense of cost security. But, I'm not getting into a comparison of these approaches. I'm just trying to figure out how to give a customer a price for an Agile project. And I've tried to say things like "what is your budget? We'll do as many of your priorities as possible within that." There is a disconnect between what clients want to know (how much for the whole thing) and the reality of what the "whole" thing needs to be and how much it will really cost.

One approach would be to simply lie. Tall the client what they want to hear. And then manage the consequences in the middle of the project. Doesn't seem like the right way though.

So instead, we've been trying to educate our clients on the tension between cost and features. In essence,
We've been using a variation on Wide-Band-Delphi-Blind to create estimates. We take the full list of features, attempt to designate tasks for implementing them, and then send that around to as many senior developers as we can -- developers with the right skill set to create an estimate for that type of project. Each estimator does his estimate alone and sends the results back to a coordinator and then we go through the estimates collectively to resolve the differences. Using this estimate of all features we then attempt to explain to our client that the estimate is under their control -- choose high priority features to implement first and then work through the list until either features or budget are exhausted.

This is not too different from agile poker (http://www.planningpoker.com/). As I understand that technique, several estimators each make a bid for how long each task or feature will take. The actual bids are not really hours. They are units. After several rounds of bidding and discussion on differences between bids, the winning bids are turned into dollars by applying the development team's velocity to the bid and figuring out real hours. This means that we have to know that velocity -- not an easy problem in its own right.

But we end up in the same place -- with an estimate for the whole project which we then have to "sell" to the client. Is there a better way?