Different results for ls when accessing Ubuntu via SSH from different clients (Windows-PuTTy, Mac-Terminal)

Sorting order is defined by the locale variables LC_ALL, LC_COLLATE and LANG (in this order, the first being the strongest). These are also some of the few variables that typically can be set by the ssh client. Check and compare these variables. You might want to set them to a well-defined value on the server (e.g. in .bash_profile), or make sure that your ssh clients set the same consistent value.

What eventually worked was the "Stop Forwarding Locale From The Client" sub-section in this answer. Just comment out out the SendEnv LANG LC_* line under Host in the local /etc/ssh/ssh_config file. Some explanation about what it does can be found here.