I finally figured out what caused the issue. In my server logs I was seeing the client IP as an internal NATed IP, but in my client logs I was also seeing the server address as an internal NATed IP.
I was using a cheap Digital Ocean instance to test and it turns out by default has a weird config with an extra 10.10.0.5 added to the interface (seems to be part of supporting some floating IP feature that isn’t even on by default):
/etc/network/interfaces
# The primary network interface
auto eth0
iface eth0 inet static
address [my-server-ip]
netmask 255.255.255.0
gateway [my-server-gateway]
up ip addr add 10.10.0.5/16 dev eth0
dns-nameservers 8.8.8.8 8.8.4.4
Somehow that address 10.10.0.5 address confuses steamworks and it reports it as its address to clients. I couldn’t figure out how to tell steamworks to ignore that address, so I just removed the line and rebooted the digitalocean droplet and now everything works great.