Most efficient way of changing 1 line in a file

Yes, sed -i reads and rewrites the file in full, and since the line length changes, it has to, as it moves the positions of all other lines.

...but in this case, the line length doesn't actually need to change. We can replace the hashbang line with #!/bin/sh␣␣ instead, with two trailing spaces. The OS will remove those when parsing the hashbang line. (Alternatively, use two newlines, or a newline + hash sign, both of which create extra lines the shell will eventually ignore.)

All we need to do is to open the file for writing from the start, without truncating it. The usual redirections > and >> can't do that, but in Bash, the read-write redirection <> seems to work:

echo '#!/bin/sh  ' 1<> foo.sh

or using dd (these should be standard POSIX options):

echo '#!/bin/sh  ' | dd of=foo.sh conv=notrunc

Note that strictly speaking, both of those rewrite the newline at the end of the line too, but it doesn't matter.

Of course, the above overwrites the start of the given file unconditionally. Adding a check that the original file has the correct hashbang is left as an exercise... Regardless, I probably wouldn't do this in production, and obviously, this won't work if you need to change the line to a longer one.

An optimization would be to use {} + instead of {} \;.

find . -type f -exec sed -i '1s|^#!/bin/bash|#!/bin/sh|' {} +

Instead of invoking one sed process for each found file, you provide the files as arguments to a single sed process.

POSIX specification of find on {} + (my bold):

If the primary expression is punctuated by a <plus-sign>, the primary shall always evaluate as true, and the pathnames for which the primary is evaluated shall be aggregated into sets. The utility utility_name shall be invoked once for each set of aggregated pathnames.

I'd do:

#! /bin/zsh -
LC_ALL=C # work with bytes instead of characters.
shebang_to_replace=$'#!/bin/bash\n'
       new_shebang=$'#!/bin/sh -\n'

length=$#shebang_to_replace

ret=0
for file in **/*(N.L+$((length - 1)));do
  if
    read -u0 -k $length shebang < $file &&
      [[ $shebang = $shebang_to_replace ]]
  then
    print -rn -- $new_shebang 1<> $file || ret=$?
  fi
done
exit $ret

Like @ilkkachu's approach, the file is overwritten in place with a string which is exactly the same size. The differences are:

• we ignore hidden files and files in hidden dirs (think .git one for instance) as it's unlikely you want to consider those (you used find ./* which would have skipped the hidden files and dirs of the current directory, but not those of subdirs). Add the D glob qualifier if you do want them.
• we don't bother looking into files that are not big enough to hold the original shebang to replace (we use . as the equivalent of -type f, so we're already retrieving the inode information from the file, so we might as well check the size there).
• we're actually checking that the file starts with the right shebang to replace, reading as few bytes as necessary (here it has to be zsh as other shells can't deal with arbitrary byte values).
• we're using #!/bin/sh - as replacement which is the correct shebang for /bin/sh scripts (#!/bin/bash - would be the correct shebang for /bin/bash scripts by the way). See Why the "-" in the "#! /bin/sh -" shebang? for details.

Errors in overwriting files are reported in the exit status, but not errors in traversing the directory tree, nor errors in reading the files, though that could be added.

In anycase, it only replaces the shebangs that are exactly #!/bin/bash, not other shebangs that use bash as interpreter like #! /bin/bash, #! /bin/bash -Oextglob, #! /usr/bin/env bash, #! /bin/bash -efu. For those, you'd need to decide what to do. -efu are sh options but -Oextglob has no sh equivalent for instance.

You could extend it to support the easiest cases like:

#! /bin/zsh -
LC_ALL=C # work with bytes instead of characters.
zmodload zsh/system || exit

minlength=11 # length of "#!/bin/bash"
maxlength=1024 # arbitrary here.

ret=0
for file in **/*(N.L+$minlength);do
  if
    sysread -s $maxlength buf < $file &&
      [[ $buf =~ $'(^#![\t ]*((/usr)?/bin/env[ \t]+bash|/bin/bash)([ \t]+-([aCefux]*))?[ \t]*)\n' ]]
  then
    shebang=$match[1] newshebang="#!/bin/sh -$match[5]"
    print -r -- ${(r[$#shebang])newshebang} 1<> $file || ret=$?
  fi
done
exit $ret

Here allowing a number of different shebangs with a number of supported options which are reproduced in the new /bin/sh shebang, right-padded (with the r[length] parameter expansion flag) to the same size as the original.