Can't ssh into remote server unless I login locally on the server first

Solution 1:

The answer was as Michal Politowski said in the comments. Encrypted home directory contained the .ssh folder, so it wasn't accessible to ssh command until I logged on locally and decrypted the folder. Solution was to create /home/ssh/%user%/ and place the authorized_keys file there, then direct ssh to look there via sshd_config. See comments for link to useful web page.

Solution 2:

It's the network adapter. It's configured to only be available to YOUR user.

You must set the network adapter to be available to other/all users. In GNOME, this is done in the network adapter settings as a checkbox "Make available to other users".

Without this, your user will need to login locally first before the network adapter starts listening for standard services like SSH.