If you look at the datasheet for the 44780 controller you can see the timing requirements, not all "compatible" controllers are equal though which is why PBP has the DEFINE LCD_COMMANDUS and LCD_DATAUS.
The defaults for those are 1500us for a command and 44us for each data byte. So if you do a clear screen, write 16 characters, move cursor to second line, write 16 characters that's a total of 1500+(16*44)+1500+(16*44) = 4408us which is pretty close to the 4ms you mention. You can always try lowering the timing values and see where it stops working.

For a serial LCD it obviously depends on the baudrate but it TOO has to write to the LCD which will then take those 4ms.

One way to get around that would be to do a buffering serial LCD controller. You could then send it data at a very high baudrate and it would then update the screen while the main CPU does other things. Or be clever and only write to the screen when and where data actually changes.

/Henrik.