I don't recommend Shiner Bock, Warsteiner, or Rolling Rock. Well, I didn't particularly like them anyway.
One good rule of thumb (not always true either): If it's typically found on tap at bars, it's no good.
Most people drink beer just because and to them "beer is beer." These people typically get the cheapest beer they can (especially in quantity) ... and that's why breweries like Papbst Blue Ribbon are still in business. Some of them don't like the so called "fancy" beers either.
If you have a data plan, browse through beeradvocate or ratebeer at the store to get an idea what you should try. In terms of beeradvocate, anything B and higher is worth trying.