We have the same problem in my company. There's a history of fixed-price, fixed-timeline projects, and our clients aren't generally very progressive.
Regarding development with no up-front commitments, I've heard so many fundamentalist agilists say, "I know it's hard, but you just need to push the benefits", or, "They might be skeptical but they'll see how well it went and come back to you next time". In some industries, maybe. In ours, that's a load of crap. I can't see any of our customers agreeing to just let us do our thing with no commitment on scope or price.
What we've found is that it's not always necessary to change the way you quote/bid/bill customers for an agile project. You can keep the agile process while sticking to your quote if you manage it properly.
Quote the way you normally would (with padding), and set some boundaries around the scope of the project. From that point on, follow your agile methodology:
- Prioritise the work with the customer - develop the important stuff first
- Develop in small iterations, showing your progress
- Collaborate with the customer to make sure you're actually developing what they want
- Grow the spec as you write the software
But more importantly:
- If a function turns out to be more complicated than what was originally requested, tell the customer immediately and make sure they're aware it will affect the timeline and/or price.
- Treat major (or even minor) changes as chargeable change requests.
You're still using Agile internally and getting the benefits, but the customer is seeing a more familiar fixed-price, fixed-timeline, fixed-scope project. Any changes cost money and blow out the time.
The hardest part about this is setting the boundaries up front. It's definitely not something that can be done by just your sales guy, BA, or project manager. You need an experienced developer in those meetings. You need to nail down the areas that could cause problems and decide on expectations.