Translation:Let's go to a different store.
It means different. Instead of saying "you are wrong", polite Japanese will say "it is different". Think of it as "it is different from what you think" so in other words you are still wrong, but no harsh words are used. The English phrase "you are wrong" is actually quite insulting. In Norwegian we say "Du tar feil" (you take error) as in you take a wrong turn or make a mistake. We do not want to describe the person with a negative word, just their actions. The Japanese do not even go that far. They just point out that reality is different from what you say.
The first case is more used. It would be used in the case of changing from one store to another in the same mall. The second case would be a very dissatisfied person who wants to go to another set of stores entirely - or possibly the case where the speaker wants to split up from the listener and go to separate places.
The online dictionary marks 違う as a verb. http://jisho.org/search/%E9%81%95%E3%81%86%E3%81%8A
It does mean "let's eat", among a few other possibilities. The -ましょうform is known as the volitional form, and it used to express many things relating to desire, will, and choice. You can read more about it here: http://selftaughtjapanese.com/2015/02/17/the-japanese-volitional-form-しよう、〜しましょう-more-than-just-lets/