Just storing the private key is fine for Ethereum.
Nope. Storing individual private key for Ethereum has same level of risk as in case of Bitcoin. The process of generating public key is exactly same for both i.e. through Elliptic Curve Cryptography. Only the process of generating address differs. Ethereum address is the last 20 bytes of Keccak256 hash of the public key whereas bitcoin address is the Base58 encoding of RIPEMD160(SHA256(public key)).
So it is advisable to use HD wallet in case of ethereum as well. Good thing is that you can use exactly same 'mnemonic words' (seed phrase) for both bitcoin and ethereum. BIP-44 has defined the standard of deriving addresses from the seed. Since you have common understanding of hierarchical deterministic process, I will tell you a little more. The seed derived from mnemonic words is first hashed using HMAC-512 hashing then left 256 bits of the resulting hash is used as 'master private key' while right 256-bits as 'chain code'.
These private key and chain code are then combined with various index numbers to produce set of private/public keys which can then used for addresses.
Bitcoin's derivation as defined in BIP-44 is m/44'/0' which means the chain separated at first hardened child of 45th hardened child of master private key will be used for generating BTC addresses.
Whereas, Ethreum's derivation is m/44'/60' which means the chain separated at 61st hardened child of 45th hardened child of master private key will be used for generating ETH addresses.
This is how same seed phrase can be used to produce addresses for multiple coins without conflicting the addresses and keys.
Just so I understand correctly: HD wallets use a deterministic algorithm for generating private and public keys. So anyone with access to the seed phrase gets access to all of my wallets? Seems like a bigger brained paper wallet hmm.
All BTC HD-wallets use the same algorithm right? So if I wanted I could just manually calculate all of my private keys in my head even without a computer if I remembered the seed? (that would definitely be boring though).
Nope, you cannot manually calculate the private keys from the seed phrase. First of all, you shouldn't manually pick the words. BIP-39 has defined the set of 2048 words which are to be picked as randomly as possible to create seed phrase of length 12-24 words. It is always advisable to use wallets to create mnemonic seed phrase for you using strong pseudo random number generator. (Note: Electrum doesn't use BIP-39 and has its own set of words)
Ok! Now that you have mnemonic seed phrase, you have to use PBKDF2 key stretching function to produce 512 bits seed. This involves 2048 rounds of SHA-512 hashing and it is no way possible for your brain to do that manually.
Once you have 512-bits seed, rest of the key derivation process is what I explained in first part of this answer.
I guess I'll encrypt the seed phrase with a good password using some algorithm and print QR codes that I then store in a lot of different buildings. Is that ok?
You don't have to do that. You can store the unencrypted seed phrase without worries. PBKDF2 key-stretching function as I explained above takes 'salt' argument. This salt argument by default is 'mnemonic' string constant. However, you can increase the security of your wallet by using custom strong 'passphrase' as the salt at the time of seed generation. Keys generated from custom salt are entirely different from the one used without it. So even if someone knows your seed phrase, he won't be able to get hold of your keys if he doesn't know your 'passphrase'. And good thing is that no one could guess if you are using custom passphrase or not so they will be redirected to empty bitcoin addresses if they try to generate addresses using your seed phrase without knowing the passphrase.
Oh, lets say I want to hodl for a year, can I just run the algorithm once to get my first address and then hold all my funds on that? Then when sending a payment I run the algorithm twice to get a second address and use that as change address, leaving the first one empty but with change in the next and then I continue like that?
Again there is no need to do that manually. Most of the wallets are well-equipped to do that automatically for you. They will automatically create change address from different branch for you when you try to send transaction.
Also, it is common practice to use different branches for change address. So your first change address won't be your second in-line bitcoin address of m/44'/0'/0' branch but first bitcoin address of m/44'/0'/1' branch.
PS: If you have hard time understanding Derivation Paths, I would recommend to watch few youtube tutorials or this thread from blue snow is good starting point as well:
https://bitcointalksearch.org/topic/derivation-path-5243350