There is a demonstration I saw that is a pretty good analogy of the benefits of Agile over more traditional methods. It's based on the game Battleship. You and the other player sit down to the normal Battleship grid. You both have 20 shots, each costing $5,000 for a total initial expense of 100,000. Here's the catch; you have to plan ALL your shots before firing a single one. Your opponent will fire his shots "normally"; take a shot, see what happens, take another shot.
At the end of 20 shots, guess who scored more hits?
The analogy translates to Agile vs Waterfall pretty cleanly; In Agile, you are able to take the sum total of everything you have already done into account when planning what you're going to do next. You will have some basic idea of the areas that will be difficult and the areas that will be easy based on difficulties or lack of difficulty you have already experienced. You also have gotten feedback from your client in smaller chunks, stating that they liked this or didn't like that, and are able to incorporate that knowledge quickly, without having built a lot of additional code on top of something the client says is wrong.
In traditional Waterfall methodologies, the entire system and the development schedule is planned out before coding ever begins. This is the "plan all shots before firing one" approach; you may be able to deliver exactly what the client asked for, but they could take a look at it and say "that's not what we need". Yeah, you get your money because you delivered according to the terms of the contract, but your developers have wasted their time, your client has wasted their money, and neither are happy with the result. Agile is designed to help with this, by allowing the requirements of the project to change while development is underway. Anything you haven't done yet is open to change; anything you HAVE already done can also change, by adding additional stories to the backlog incorporating the amendments to the current product.
Also, because the client gets to decide what you work on first, and with you delivering small chunks of completed work more often, the client could conceivably have a system they can use sooner. That's visible ROI to your client, which usually makes the client more willing to buy in to this more involved development process.