6502.org

Indeed, I also find it very helpful to go back and double check my wiring to make sure I didn't make a mistake somewhere, or forget something. When you start adding more and more lines for things (Address, data, control) it becomes easier and easier to miss something somewhere.

Imagine trying to wire up a modern 64-bit CPU by hand!

I've got good news, and good news only. It really was the LCD!
I read the datasheet for the LCD's control chip and it specified a minimum enable pulse of 450ns, so I assumed it wasn't the problem since it couldn't run even at 500KHz. I gave the datasheet another look this morning and found that the busy-flag cannot be read before the LCD is fully initialized, and that some pretty hefty delays are required between the initializing commands. I'll definitely have to try adding those delays and see if this whole thing could've been solved in software.
I have come to the same conclusion. I wanted the LCD to be easier to interface with when writing the assembly but I no longer feel that the saved instructions are worth it.

That's good news.  I have working sample LCD-driver code in various forms in the 6502 primer section of my site, at http://wilsonminesco.com/6502primer/LCDcode.asm which I recommend following, particularly as there's a trick in the initialization code without which you can sometimes have problems.  It doesn't always show up in the data sheets, but we received it from an applications engineer many years ago to solve a problem at work.  Since then, I have used these LCDs in many projects and never had any further problems.

I do recommend going through the entire 6502 primer, indexed at http://wilsonminesco.com/6502primer/ . It was originally written in 2002 (although it collected dust for a few years until I had my own site) to address problems that newcomers kept bringing to the forum, and I keep updating and improving it as the need arises.