> Instead of doing the shebang line, it has to traverse the filesystem to resolve the link. I suspect that’s probably more expensive than parsing the shebang line.

I highly doubt that. Path traversal is one of the most optimized pieces of code in the Linux kernel, especially for commonly accessed places like /bin where everything is most likely already in the dentry cache. For the script with a shebang on the other hand it first has to read it from disk (or the page cache), then parse the path from it, and then do a path traversal anyway to find the referenced file.