At long last, I figured out the problem. If perform this command:
$ sudo launchctl list | grep bootp
1550 - com.apple.bootpdYou 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.bootpdThen, re-enable Internet Sharing. You should now see something like:
$ sudo launchctl list | grep bootp
3423 - 0x100101440.anonymous.bootpdThis is the anonymous Internet Sharing version of bootpd. Now it all works.