As always, you can't be paranoid enough
It really comes down to an issue of technical competence and trust.
If someone is technically competent enough to make their own clean Ubuntu OS, install a well-known paper wallet generator from github, and validate its signature -- then for sure that's the best route to go. I've even provided step-by-step instructions
https://bitcoinpaperwallet.com/ubuntu-linux-live-bootable-cd/ to share what I learned about this process.
However, for someone who just doesn't have those technical skills (or a friend with those skills), then why not consider a CD which can fairly easily audited by this community. (In fact, I'm planning to post bounties for 3rd party security audits.) A high degree of paranoia went into the production of the CD, from the mastering all the way to the delivery process.
For example: CDs are sealed with tamper-evident serial numbers, and purchasers are notified via email what serial number to expect. (This way the postman or a roommate can't slip in a bogus CD.)
I agree that you can't be paranoid enough, and I assure you that all my paranoia went into the development of this CD.