> How is (home) NAT making the problem more complex than a stateful firewall?

ICE/TURN/STUN: the address that your software sees on your laptop, desktop, home NAS is not the address that clients can connect to.

In both NAT and non-NAT you have to use UPnP/PCP to do hole punching, but with NAT you have to do a bunch of address-y stuff as well.