I'm trying to figure out the worst timing I could possibly use to update an 16 character by 4 row LCD display.

Currently I have a timer that executes (as an interrupt) every 60uS in order to send the next character or command in a buffer to the display. The problem is in that interrupt, variable saving and restoring and entering and exiting the interrupt takes up about 15uS.

To reduce the frequency of the interrupt, I'm intending to increase the amount of waiting time before a character or command is sent to the LCD.

The question is just how high of a delay can I go before the user can believe the LCD is processing characters too slowly?

Currently my buffer for the LCD is about 16 bytes and Ill be lucky if I can extend it to 32 bytes because the rest of the ram is used for other functions and I do not have external memory for the board.

In other parts of my program where it wants to fill the buffer, I have the program wait until the buffer is empty again.

Human perception is in milliseconds, so you won't hit that easily. LCDs have 2 basic time constraints: commands and characters. I process character strings all at once, using the busy flag to pace the transfers. Most of the time commands are 1 or 2 so a simple delay is fine. You can also send a command, start a timer, go do other stuff then check the timer. Or, set a counter, go do other stuff N times where N is enough time in execution loops of stuff.

About 50ms or slower is where humans begin to notice lag. (Consider that most movies are filmed at 24 frames per second, which is just slightly faster than that.) With character LCD displays the pacing item, as CustomSarge pointed out, is the BUSY flag of the LCD. Most of these displays are so slow to write (many milliseconds) that just checking the flag from the base loop is adequate. If yours can write in 15uS you've got a fast one.

Another idea is to not use an interrupt, but poll the buffer in some place in your program, i.e. if you have an idle loop, use the dead time to update the LCD. 

You can create a fifo or circular buffer and write characters into it, then pull them out in the idle loop.  Saves the interrupt overhead.  

Thats an idea but I gotta watch some of my loops because they execute pretty fast (like under 20uS for pure idleness) and that won't be enough of a delay for an LCD character. Thanks all for your help.