Proposing Agile is like recognizing you are not really sure what to do and you need several tries before figuring out. This isn't going to help build trust with your customer, right?
Actually, with IT being such a young domain and rapidly changing, waterfall is the wishful thinking you envisage before the project start; while Agile is the harsh reality you end up with. The only question is: how long do you want your first iteration to be?
I like the picture below, since it speaks in very little words about Agile versus waterfall. It shows waterfall is just Agile with a very very long first iteration. Also, it illustrates how the project outcome is blurry at the beginning; going straightforward towards that vision does not mean you won't need some iterations before the outcome becomes clear. With Agile, you will take a more sinuous approach, but will end up with a shorter path in the end.
Thank you, Dorian, for the drawing!