Justin, you are correct, and the salesman was full of bull. He had the set mis-adjusted. Wide TVs can be set to stretch the picture to fill the screen, but most of them only stretch out the outer edges, so the middle third is not so distorted.
There is more than one way to view a 4:3 picture on a widescreen TV. The TV can be set to 'zoom in' so the picture reaches the sides without stretching, but you lose top and bottom info, or, as you surmised, side bars can be added. (Actually, they aren't 'added', the scanning beam, or 'raster', simply starts and ends without exciting the phosphor spots along the sides, so the sides appear dark.)
Also, there is more than one way for a TV to display a wide picture. The term 'anamorphic' refers to the process of intentionally pre-distorting the picture with lenses, and displaying the picture by un-distorting the picture with lenses upon playback. (At least, in movie theaters with real film, lenses are used. It's done electronically in widescreen TVs.)
The purpose of 'squeezing' the picture, instead of simply not using the top and bottom bands as done on widescreen (letterboxed) laser discs and non-anamorphic DVDs, is that the entire height of each frame is used, which allows for the maximum vertical resolution. Letterboxed movies simply don't use the top and bottom several lines (several dozens, actually), so when the picture is enlarged vertically on a widescreen TV, fewer lines of picture are spread out to fill the screen vertically. Hence, less resolution than the TV is capable of.
When you saw the distorted picture in the store, the 4:3 picture was stretched to fill the screen, which required exciting more dots than the non-distorted picture required, so larger actually meant less horizontal resolution.
Most people don't know this, but widescreen movies are actually 'clipped' top and bottom to some extent. This allows for masking props, microphones, and the like, as well as allowing for less picture loss when the movie is shown on a non-widescreen display. Compare the widescreen and standard sides DVD of A Bugs Life sometime, comparing the distance between characters' heads and the top of the screen.
