As suggested, I placed coupling capacitors between VCC (pin 16 on the 595N) to GND, and GND to GND (the second one was just in case). It didn't change anything. In the LCD3Wires tutorial, a decoupling cap is recommended for pin 12 to GND, to cancel out ripple which could cause flicker. I had this cap placed between pin 12 and pin 13, since pin 13 is tied to GND, and electrically it is all the same. To ensure that this was not the issue, I removed the cap entirely. When I did this, I can definitely see the flicker when the SR changes state (clock), and the LCD now writes garbage faster, and generally to only the first 6 blocks. If I hit the reset button on the Arduino, or remove power from it entirely, the LCD does nothing (I am running it off of separate power from a USB port). It holds the state of the characters until the Arduino is powered back on, then starts to write garbage again.