What's worse is that the terminals are fine.
I doubt so. This is a much more complex story than you probably think. Terminals behave differently, and one's behavior might be right-to-left friendly with a certain set of applications, while others' behavior might be RTL friendly with another set of apps.
Local files are displayed correctly.
Again, it highly depends on what you mean by "displayed": do you cat them, or open with vim, emacs, less, some other application, etc. Maybe with some terminals cat gives the expected result and vim the unexpected one, with other terminals the other way around.
You might be interested in this, an about 50-page long technical document studying the situation and proposing a way to address the problems, so that a terminal can support multiple modes, and as such support the seemingly contradicting requirements of different kinds of apps.
VTE version 0.58 implements the proposed solution. VTE is the terminal emulation engine used by lxterminal and xfce4-terminal, along with many other terminals. Whether you see the "good" or "bad" behavior in these software might thus easily depend on VTE's version. However, again, it's possible that you find the old behavior the "good" one and the new the "bad", depending on what types of applications you test with. In this case, with VTE >= 0.58 you can use the escape sequences mentioned in the document to switch mode, e.g. printf "\e[8l" to revert to the old behavior.
ssh is irrelevant, apart from a software's local or remote version possibly being different.