I did some digging.
The shell script part of this seems to be related to the expanded XProtect coverage in 10.15. When running a binary/script/thing for the first time XProtect is going to check it to see if it's known malware. If it's unsigned then it adhoc signs the binary and checks the hash. It's not really notarization per se, but it does use the term "legacy notarization" in the logs.
https://opensource.apple.com/source/Security/Security-59306.80.4/OSX/libsecurity_codesigning/lib/policyengine.cpp.auto.htmlIt seems you can disable this process by adding your terminal program to the Security and Privacy control panel as a Developer Tool as well.
If you have really bad internet connectivity I could see this causing a delay the first time you run something. But this would only cover the shell script case for me. It wouldn't explain things like the long delays to launch apps.