You are somewhat correct. There needs to be a DNS record in order for Cloudflare to do anything with it. If you don't add www. then Cloudflare isn't actually seeing the request come through.
However, it does not need to be a CNAME. Actually it should be a dummy record... ie a record that points to cloudflare's reserved dummy ip just for this kind of stuff.
What's the best possible configuration? I'm not technical enough to understand all the details of this subtlety, I just want the redirection to be done properly and not be penalised.