At long last, I figured out the problem. If perform this command:
$ sudo launchctl list | grep bootp 1550 - com.apple.bootpd
You will see that bootpd is actually running, but being com.apple.bootpd means it is running as the normal system bootpd server. You don't want that.
First, disable Internet Sharing. Then run this command:
$ sudo launchctl remove com.apple.bootpd
Then, re-enable Internet Sharing. You should now see something like:
$ sudo launchctl list | grep bootp 3423 - 0x100101440.anonymous.bootpd
This is the anonymous Internet Sharing version of bootpd. Now it all works.