Ok, I did some further testing.
I confirmed that I can replicate the problem reliably by replacing my 74163 with the stock HDL 74163. From the design I last posted, replacing the 74163 in UartSend with the Atlera stock 74163 will make it fail as I mentioned in the OP.
I put my 74163 back in and inserted the frequency counter that I drew (which is a proven design) and it falsely reads 40X the baud rate, not 16 like it should. The echo'ed characters are correct for some, but not all. For example, pressing Shift-S echos "s" and pressing just s echos 's' as well. So by this, I can conclude that the frequency counter circuit is failing and the baudX16 clock is obviously correct.
Now when I swapped the 74163 again and used the stock HDL version, now everything works - frequency counter, baud generator and character echo. The display is connected to the frequency counter in this configuration.
This is clearly some kind of routing error on the part of the compiler.
Interestingly enough, I do have a small amount of HDL code in the frequency counter. I got lazy and used a stock HDL multiplexer instead of drawing it out myself. Also, the baud rate generator has an HDL constant.
I'm starting to wonder if the number of HDL circuits matters - odd works, even doesn't. I might see if I can replicate this with simpler circuitry and submit it to Altera as a bug.