The sensor isn't perfect, if you aim even a really, really good sensor (Better than the, um, 'classic' Sharp IR sensors) at the same spot on the wall and take a few readings, there will be some variation. If you discard some number of least significant bits, it's possible to get the same reading every time, but your readings will be more granular. You should probably keep the maximum precision, and then try to fix errors in software (i.e., change your data so that an almost straight line really is straight).
What sensor are you using, and what range of measurement do you expect? The output of the sensor is very much nonlinear. This graph (from the datasheet) compares the output voltage on a linear scale with the distance:
You'll notice that it looks a lot like the graph of y=1/x, i.e volts=k(1/distance). This can be used to get a decent first approximation, but division on an Arduino is expensive. You'll have better luck calibrating the sensor and storing the voltage/distance pairs in a look-up table (in program memory, of course). This one comes calibrated from the factory such that a measurement at precisely 24cm measures to 24cm +/- 3cm. Unfortunately, they don't give you a way of knowing what the voltage at 24cm should be except by squinting at this graph.
The sensor will have higher precision at certain ranges. Imagine that there is a random variation of, say, +/- 250mV in your readings (Gaussian if you like, but random is easier). It's hopefully a lot smaller than that, but it makes it easy to visualize. The variation means that your readings with this sensor at, say, 50cm or 70cm will vary over 20 or 30cm, but measurements at 15cm should be within a few cm. This sensor is rated for 10-80cm, but you'll get more accurate readings if you only trust it for 10-25cm or so. If you're controlling the robot, you should be able to move to these distances and get the best readings.
The sensor draws current in large bursts and is probably mounted on a fairly long cable. A capacitor will help stabilize the readings. Don't jam it into the JST; solder it to the PCB on the back. It's drawing a lot of current and it's pretty slow, so small capacitances traditionally used for decoupling (0.1uF) probably won't work. I'd use a 10uF 1206 or 1210 ceramic SMD cap in parallel with a 100uF electrolytic. If you find that high frequency noise is still present, add a 0.1uF 1206 on top of the 10uF. Here's a picture of the locations for soldering (original image from Sparkfun):
You could also try adding a small capacitance on the Vo line to smooth the output. You should experiment to see whether or not that helps. I'd keep it below 100pF, starting at around 10pF. This will create a moving average of the readings in hardware. More circuitry (a series resistor) would enhance the effect, post a comment or another question if you want to build a more complex low-pass filter system for this purpose. Note: The Sharp sensor may not handle driving into a large capacitance well, and might balk or break if asked to change the voltage quickly. It's also possible that it's a single-sided output, and might require a resistor to ground to discharge the capacitor if you add more capacitance than is currently present in the parasitics.
Twisting the cables together will help reduce noise coupled on from external sources like 60Hz mains. Keeping them short will also help mitigate noise.
No, you don't need to refresh static LCDs anywhere near that fast. 60Hz should be fine- which will give you a couple years of battery life if it scales (it's normally in the range 30-100Hz).
The main thing is that you need to make sure that the average DC voltage from each segment to backplane is very low (like < 50mV). Easy when you're driving it with CMOS push-pull outputs. You must drive the COM high/low with a 50% duty cycle (very close to exact) and drive the 74HC595 outputs high/low in sync either inverted (on) or not (off). If you want to blank the display make sure no DC voltage appears across the display (the reason for this is that DC voltages cause electrochemical action which can permanently damage the display). It doesn't look like you are doing that.
Here is an application note from Atmel that shows how to do it with a microcontroller, showing the proper waveforms:
So probably the best way would be to wake up, flip the COM and RCK the new data in from the shift registers (perhaps alternate doing COM or RCK first), then calculate the next frame segment data, shift it out to the HC595s via SCK without transferring to the output register and go sleepy-bye. Repeat forever.
Best Answer
The legally correct answer is "anything can happen": you operate a component outside its specs, so you are not allowed to count on any specific behaviour.
My best guess is that the display will flicker, or maybe (if you are unlucky) will not operate at all.