If you try to convince your customer (or boss, management, colleagues, etc) to do something totally differently to how they've been used to doing it, then they'll react in one of the typical ways in response to change: acceptance, panic, refusal, etc. So, I recommend a gradual adoption of Agile methods until you're there, for example:
Start by having weekly meetings with the customer to discuss the 'prioritised requirements' (Feature Backlog). Ensure the priorities are set by the customer and are in Story Points units (with guidance from you).
When you add items to the list, write them in 'User Story' language, but familiar enough not to confuse/alienate the customer. If you've already got some kind of specification or use cases, adapt them, but don't be tempted to totally re-write them - the customer likely won't be able to make the leap.
Have regular deliverables so that the customer can see progress and the benefits of the new way of working. Make sure they know what they've just received, how to get to it (URL, download site, etc) and follow up to make sure they've tried it.
Get feedback on these deliverables at the next weekly meeting so that the customer can refine the Feature Backlog according to what they want to see next. Take the time to outline this 'choose top user stories, implement, deliver, review' mechanism to introduce the concept of an 'iteration' or sprint.
Assign cost estimates to each User Story so that the customer can understand the effort required to achieve each User Story and can learn how much could be achieved in one iteration. Be open with the customer about the Planning Game used to come up with the estimates.
Make sure the customer can see how many User Stories have been achieved so far (budget used) and gets a clear understanding of how many of the remaining stories could be completed in the remaining time/budget.
I've done this successfully with multiple customers and found that after delivering on promises for a few weeks, they totally trusted us from then on and focussed more on which features they wanted most urgently rather than whether or not we were going to deliver. We didn't necessarily expose them to all the terminology, but they 'got' the regular updates and open-and-honest discussion about what features get implemented next.
There's nothing scary, wrong or weird about iterative project methodologies (such as Agile, XP or Scrum), its' just not the 'traditional' Waterfall method. Having a nice human explanation helps:
In traditional construction, you can't alter the foundations without
first tearing down a house/office block/bridge. This is one reason that
you have to get the foundations right first before moving on to the walls
In other industries, you can change any part of the system without having
to start again. For example, in Formula One, you can jack up the car
to change the wheels - you don't need to disassemble the whole car.
Therefore, some projects are very suitable for a iterative/cyclical approach where
the initial solution is refined many times until it is just right.
I've deliberately been vague with the Agile terminology in order to convey the message easier and I've had a long day so may have got a bit muddled in there.