Long term BTC investing my question is, what is the safest way of buying and holding bitcoin for the long term? 
And I mean 10-20 years, either a lump sum or through dollar cost averaging, is a paper wallet the answer? Or maybe a cold wallet? I am looking for something very safe that will likely still be around in 20 years time
Recommendations for how or where to buy Bitcoin are generally off-topic here, but long-term storage is a fair question. 

First, understand what owning Bitcoin really boils down to: having knowledge of the private key that allows you to spend the Bitcoin stored at that key's address. You aren't storing the bitcoins themselves persay, you just need to store the private key (a 256 bit number). 

These days, there is an industry standard that is known as 'hierarchical deterministic (HD) wallets' (BIP32) that allows more efficient wallet backups, and there is also a related standard (BIP39) that allows you to create a mnemonic seed phrase that works as a human-readable master backup of your wallet. So rather than storing a single private key, you can opt to store a seed phrase instead. Since it is a standard, most wallet software is compatible. 

Whether you are storing a private key, or a seed phrase, it is probably a good idea to make multiple copies, in case something unexpected happens (fire, theft, etc). By storing them in geographically diverse locations, you can avoid having a single point of failure. The medium of storage can be important too: just writing it down on a piece of paper isn't as permanent as stamping it into a piece of titanium. How involved a solution you choose will depend on your personal situation. Generally, I would recommend a physical storage solution for the length of time you've mentioned (10-20 years), as a digital storage solution may experience data degradation within that time. 

One issue with the paragraph above is that if you create multiple copies, and one of them is found, then whoever finds it could spend your coins. So (as Raghav mentioned) BIP38 is a standard that will allow you to encrypt the key with a passphrase (note: BIP38 is less commonly implemented than BIP32/39, but it is still available). Keep in mind that now you will need to store the encrypted private key, and also the decryption passphrase, so this adds additional consideration. 

There is also the option of using a multisig address, which can only be spent from if m-of-n keys are used. So you could, for example, create 3 keys, but only require 2 of them in order to spend the funds. If you disperse the keys geographically and one of them is found, the finder will not be able to spend your coins (as they'll still need one more key). You can create all sorts of interesting custody setups using multisig addresses, and there are even Bitcoin storage services that offer solutions using such constructions. 

It is up to you as an individual to decide which sort of construction you are comfortable with, there really isn't a 'one-size-fits-all' when it comes to long term storage.

So a related question is: what is the best way to generate a private key (and its related address)?

Generally, you will want to use a device that you are certain is clean (not infected with any sort malware). A 'cold wallet' just refers to a wallet whose private keys have never existed on an internet connected device, thus removing many attack vectors by which someone could steal your private key(s). For high-security storage, it is definitely recommended that you generate keys on a machine that does not connect to the internet. This could just be a special-purpose laptop, or a hardware wallet, etc. Again, there is no 'perfect solution', what you choose will depend on your situation.