It was mentioned once before in this thread, but I'll shine a bit more light on this solution that worked for me. The only fix that worked for me was to disable my VPN or turn on "Local Network Sharing" inside my VPN's settings. It seems that having the VPN disallow local network sharing prevents sidecar from working for some reason.
VPNs commonly come with the "Local Network Sharing" option disabled, and this appears to prevent sidecar from working. When I disconnected my VPN, sidecar started working. Enabling the VPN again caused sidecar to no longer connect. With the VPN still connected, I went into my VPN's settings and enabled "Local Network Sharing." This worked. Now the VPN is still connected and sidecar works.