Agile introduction is an interesting problem. One that I have learned to avoid. I am not feeling comfortable standing up to a business owner and saying (paraphrased, of course), "if you will do it my way, your life will be better". At least, not about development methodologies, I have no problem saying that about techniques, design or tools. The reason that I don't feel comfortable saying that is that there are too many issues surrounding agile introduction to talk confidently about the benefits.
I usually never mention agile to the customer at all. What I am doing, however, is insisting on a regularly scheduled demo. Usually every week or two. Oh, and I ask the customer what they want to see in the next demo. Given that I have a very short amount of time between demos, I can usually get a very concise set of features for the next demo.
Having demos every week or two really strengthen the confidence in the project. So from the point of view of the customer, we have regular demos and they get to choose what they will see in the next demo, that is all.
From the point of view of the team, having to have a demo every week or two makes a lot of difference in the way we have to work. As a simple example, I can't demo a UML diagram, so we can't have a six months design phase. Having to accept new requirements for each demo means that we need to enable ourselves to make changes very rapidly, so we go to practices such as TDD, Continuous Integration, etc. It also means that the design of the application tends to be much more light weight than it would be otherwise.
In other words, everything flows from the single initial requirement, having a demo every week or two.
Once you have that, you have a free reign (more or less) to implement agile practices, as they are needed, in order to get the demo up and running. You get customer involvement from the feature selection for the next demo, and you get customer buy-in from having the demos at frequent intervals, always showing additional value.