Thanks for the education! So, is it fair to say that an output is always always associated with 1 or more addresses (either through a hash of a public key, or a hash of multiple private keys)?
No.
An output is associated with a script. That script may, or may have any of (
or none of) a one or more public keys, one or more public key hashes.
I have to admit, I don't fully understand the case where there's "no valid address that the output script could be represented as" except under the case where this is true because of a payment to a multisignature conjunction of addresses. Please forgive my ignorance.
A script encumbers the output with some requirement that must be met in order to use that output as an input to a new transaction. There are a couple of very common scripts (P2PKH and P2SH) that have been defined and given a version number. This defined "script version" allows the entire script to be represented with its version and its data. In thses common scripts the data is a hash (a public key hash in the case of P2PKH, and a script hash in the case of P2SH) The version, hash, and a checksum are then encoded as an "address".
However, it is possible to create scripts other than these common script types. It is also possible to create scripts that do not contain a hash or a public key at all. In that case, there is no recognized version number that represents the script and therefore no agreed way to represent the output as an address.
Again, can you help me understand the "none at all" case?
As a simple example take a look at this transaction:
https://blockchain.info/tx/8bae12b5f4c088d940733dcd1455efc6a3a69cf9340e17a981286d3778615684There are two outputs.
One was sent to: 1HnhWpkMHMjgt167kvgcPyurMmsCQ2WPgg
The other was sent to an output that has no representable address.