Why does my zsh program run fine in terminal, but not as an automator app?
This is the standard issue with GUI apps in macOS. These are launched via lanuchd from desktop, no part of the process has run through a shell so what is in any of your shell start up scripts e.g. $PATH does not matter.
What you need to do is use the full path to anything you call in your case the full path to youtube-dl and if that is a script that might need editing to provide full paths to what it calls.