The answer was simple but not obvious:
Instead of:
git clone https://github.com/org/project.git
do:
git clone https://[email protected]/org/project.git
or (insecure)
git clone https://username:[email protected]/org/project.git
(Note that in the later case, your password will may be visible by other users on your machine by running ps u -u $you and will appear cleartext in your shell's history by default)
All 3 ways work on my Mac, but only the last 2 worked on the remote Linux box. (Thinking back on this, it's probably because I had a global git username set up on my Mac, whereas on the remote box I did not? That might have been the case, but the lack of prompt for a username tripped me up... )
Haven't seen this documented anywhere, so here it is.