The lack of clarity is even worse in my case, because my domain and my webspace are hosted at different companies.
The change only needs to happen at the registrar.
When I go into the control panel of my domain host, most of these subdomains are also there - but with other IP addresses. Shouldn't they be the same? Should I change my host's IP addresses to the ones Cloudflare presents?
This is what was picked up when we picked up the records from the registrar. If the actual hosting IP is different, then you should edit the subdomains to the correct ones on the CloudFlare DNS settings age.
Should I add all the subdomains that I can find on my subdomain's host to Cloudflare?
Yes, if they weren't picked up during the signup process. We will only pick up common subdomains (blog, mail, forums, etc.) during the signup process, but will miss things like if you dogs.yoursite.com, etc. (not common records).
Is it possible that I do not have to change any settings on my webspace hosting?
You do not.
Should I change the name servers of my domain host, or the name servers of my webspace host? (The latter didn't seem possible, so I suppose the answer will be the former.)
You change from the nameservers on file at your registrar to ours.