What are the origins of "Download", "upload", "downstream", "upstream", and why are they respectively down or up?

Solution 1:

Water flows downhill. (I'm aware this is not new information ;)
The supply is at the top & the receiver [eventually the sea] is at the bottom.

Downstream is further from the supply, being supplied from upstream.
Upstream & downstream, or upriver/downriver are expressions probably as old as language itself to determine a direction in a stream/river without any need of compass direction.

Radio & television were one-way communications - so the broadcaster, ie the 'server', is upstream & all the listeners/viewers downstream of that.

Upload/Download simply follows that convention.

Addition after hitting HNQ list & attracting more attention than originally envisaged…

I think once you have the basic 'water-flow' analogy, from before we even knew what electricity was, let alone broadcasting or the modern cloud/server/CDN/client etc etc, everything else just follows logically. It only needed one person to make the initial connection - & we may never know who it was - back in the early days of radio, or even if radio was first to use it… it might be harder than who coined the term "broadcast" - https://en.wikipedia.org/wiki/History_of_broadcasting - which does have an answer.

Solution 2:

Initially, "download" and "upload" were used in aviation, especially by the US military. "Download" meant to remove items such as weapons from the aircraft, while "upload" meant to load items onto the aircraft.

For example, the August 1963 Aerospace Maintenance Safety (a publication of the US Air Force) says at page 18:

Failure to follow written procedures and download the missiles...

(meaning failure to remove the missiles from the aircraft)

Then, within the US Air Force, the concept was extended to computers.

The July 1968 IMPLEMENTATION OF THE USAF STANDARD BASE SUPPLY SYSTEM: A QUANTITATIVE STUDY says:

ADC provided a three-man team, which visited the bases some 30 days prior to conversion and conducted a full-scale download of the 305 and upload of the 1050, requiring 10 to 15 days.

where "305" means IBM 305 RAMAC and "1050" means the UNIVAC 1050

The terms "downstream" and "upstream" were used independent of "download" and "upload" in the early days of cable television.

For example see the November 1971 Interactive Television, Prospects for Two-Way Services on Cable which has a nice explanation:

One-way cable television systems distribute signals from a central point -- the headend -- to many subscribers over a party-line or "tree "network (Figure la). Everyone receives the same "downstream" signals on his cable at the same time.
...
Two-way cable television services require information flow "upstream" from the subscriber to the headend or among subscribers themselves.