How do I change, turn off this? I get a popup telling me that I'm behind a firewall that's NAT protected and may cause problems letting me connect and join others.

you need to access your router. google it.

I did the only option I had was either ON or OFF. I turned it off and I lost my internet connection.

There are actually different NAT types, but I guess that's not the real question if you had just "on/off" button on router... keep it on and if you have any software-based firewall on localhost, let crysis access to the internet. As long you don't run a server, you don't need to forward any ports.