The Wi-Fi connects when the Arduino is powered by my computer and a serial console is connected, but not if I plug into an outlet.
It seems this is a power issue. I am powering the esp8266 from the Redboard 3.3v line that is only rated for 150mA. I will be switching to the 5v line with a 1A regulator.
I also switched to 9600 baud for communicating with the esp8266, added retries around all of esp8266 commands, and added reconnect logic in case the esp8266 reboots. With the changes, it works okay even with the underpowered 150mA line.
It's still a mystery to me why it works so well when connected to my Macbook.