In *nix environments, the permissions and privileges of a running executable are determined by the user who executes the program. You’ve verified this by noticing that when you run wp-cli with sudo, what it can do changes – you didn’t need to change the permissions on the executable to do this, you ran the program as root and the executable took root’s privileges. This is also understandable as when you’re logged in as a different user, the same executables can do different things – it’s the user running the executable that changed, not the executable.
(I also note that install instructions for wp-cli don’t mention anything specific re. privileges, and would if they needed to. https://make.wordpress.org/cli/handbook/guides/installing/ )
There are exceptions to this, the setuid (Set User ID) or setgid (Set Group ID) bits allow an executable take the permissions of the user or group that owns the executable, but this is probably not required here.
So, it sounds like if wp-cli does not have permission to write a file when you run it as a particular user, assuming you haven’t used the setuid or setgid bits, then you may want to double double check that the user you’re running it as actually has the permissions required for wp-cli to write a file, or do whatever it needs to. I suspect this is the case.
The approach here to solve your issue would be to simulate what wp-cli is doing using the user you’re running it as. E.g. if you get an error that wp-cli can’t write to a file in directory /var/www/foo/wp-bar, then the first thing to do is e.g. touch /var/www/foo/wp-bar/test, and this should also give the same permissions error, then resolve this using whatever setup makes sense for you in terms of the user you’re running wp-cli as and apache both having write permissions to those files. SO/SE will abound with help with that, e.g. https://askubuntu.com/questions/1115979/apache-permissions-to-allow-both-user-and-web-server-to-edit-var-www
(Edit: If this approach doesn’t work, then post the error from wp-cli, and the error you get from manually carrying out a similar operation using the user you ran wp-cli as, and that should give extra info to be able to resolve, however that’s a general Linux permissions issue rather than specific to WP)