If they need to talk to each other directly, you get both clients to send stuff to each other using the central server to decide on a common port and figure out what ecah other's IP address is.
When each client sends packets to the other on the correct port, most NATs will see it as expected traffic and route it correctly. (A sends a packet to B on port 2000, this is blocked by B, but then B sends a packet to A on port 2000, this is accepted by A because it just sent a packet to B on that port, now A sends another packet to B and B accepts it now because it had previously sent a packet to A.)
If you only need the client to talk to the server then it should just work with NAT, provided you return packets on the same port that they sent them from (meaning you can't use 5 ports like HL2 does). This should just go right through NAT.
Now that I think about it, most firewalls will still block this, other than the built in Windows and Mac OS (I think, haven't tested it and I use Little Snitch) firewalls. Hopefully if the user has more than these permissive default firewalls installed, they will be adapt enough to configure their own firewall to let your traffic through.
I hope I'm not steering you wrong, it's been quite awhile since I had to do this kind of thing (haven't been in school for, oh what, three years? ;)
[Edited for clarity, though I doubt it's any clearer.]
When each client sends packets to the other on the correct port, most NATs will see it as expected traffic and route it correctly. (A sends a packet to B on port 2000, this is blocked by B, but then B sends a packet to A on port 2000, this is accepted by A because it just sent a packet to B on that port, now A sends another packet to B and B accepts it now because it had previously sent a packet to A.)
If you only need the client to talk to the server then it should just work with NAT, provided you return packets on the same port that they sent them from (meaning you can't use 5 ports like HL2 does). This should just go right through NAT.
Now that I think about it, most firewalls will still block this, other than the built in Windows and Mac OS (I think, haven't tested it and I use Little Snitch) firewalls. Hopefully if the user has more than these permissive default firewalls installed, they will be adapt enough to configure their own firewall to let your traffic through.
I hope I'm not steering you wrong, it's been quite awhile since I had to do this kind of thing (haven't been in school for, oh what, three years? ;)
[Edited for clarity, though I doubt it's any clearer.]