The best solution when dealing with firewalls is to work with the firewall vendor to get oracle configured to pass through the firewall.
Oracle does not support pass through a firewall directly. They have alliance with different firewall vendors and provide them with connection manager which they modify to work with their firewall.
The next option is for you to configure connection manager.
The linux client is most likely experiencing slower response time, because it is trying more paths before it failes. Try to edit the SQLNET.ORA in the oracle_home/network/admin, net80/admin or where the TNSADMIN points, either remove the sqlnet.expire_time or set is to some value like 30. Then stop and restart the listener for the change to take effect.