You could run few queries with IO Stats on them and show them it takes x seconds to run without up-to-date indexes and x seconds with them.

Also explain to them if you wanted to search for an address in a phone box and never had an index at the beginning of it would it take you a long time to find it or would it be better with an index.

The problem is to convince non-technical people what it is and also why to do it. There are many DBA that will run things without knowing why so a few diagrams and statistics works wonders.

Good luck