I don't think that's really a problem you can solve regardless. A STUN server would make most NAT irrelevant anyway. Most firewalls are setup to allow established connections, so you just need to create an outbound connection to allow the inbound. You can basically use the same techniques as SIP/RTP when they do NAT traversal.

PCP is better than UPnP IGD, most importantly because it time limits the opening so port reuse is easier. I wouldn't use either in practice. I wouldn't suggest NAT-PMP either. I wouldn't use port forwarding if I could avoid it as well. I'd use destination NAT with a source IP range I knew in advance so it wouldn't show as easily in port scans. Someone is likely to tell me why that's a terrible idea, but it's my (current) preferred method.