The answer really depends on who you plan to give it to and what they can ingest. CineForm is an extremely high quality intermediary codec which you can obtain for free (you use to have to buy it) by downloading GoPro Studio. This will require that whoever you give it to can read CineForm files. Sony YUV is another high quality AVI codec that Vegas Pro supports. The question is, can your client read them?
Since the industry standard for high quality delivery is Apple ProRes MOV file, I find it odd that you want to deliver an AVI file so I assume whoever you are delivering this to has specifically requested an AVI file. You might want to ask them what codec they would like you to use since there is no standard and whatever you use (other than uncompressed) they need to be able to read.
John's advice is all good, but of course he had to make assumptions due to the lack of information. My main concern would be that since it's being played in department stores, I'd pessimistically assume they're going to be played from some ten year old entry level Dell in a cabinet somewhere that's not going to be able to read any fancy third party AVI codec. I wouldn't make one more assumption and immediately get with the client to hash out every technical detail.
If this is one of those horrible situations where the people who hire you simply have no idea and won't put you in contact with the kind of people who may actually know, I always opt for maximum compatibility over highest quality. Nothing pisses off a client like getting a video they can't simply click on and play.