Age of Empires has a very nice feature: two people can play the same civilization, as a single player. This is different from teaming up, because you can give conflicting orders to the villagers. My wife and I love to play this way, especially when we can play against... I mean, with... our other friends.
Unfortunately, if you want to play with multiple players behind a firewall, and at least one player outside the firewall, you're out of luck: DirectPlay doesn't allow you to remap the ports.
One solution is to set up a VPN. That way the players behind the firewall can keep their IP addresses, and the players outside the firewall look like they're on the local LAN. Businesses often use a VPN service, and one even comes with Windows (PPTP). I recently set up a gaming LAN with OpenVPN. Here's how.