I'm confused - you're all talking about different things. Guarddog and Firestarter aren't firewalls, really, they just provide a nice GUI interface for Linux's iptables firewall and monitor the logs for you. Outbound connections are sometimes important to secure; I have mine set rather restrictively, although I have very little software on my system that would ever want to "phone home" to begin with, so it's pretty easy to enable the ports and services I use everyday.
Firewalls generally have very little to do with viruses, given that most use already commonplace media to propagate, and on Linux this isn't really a problem anyways; the only viruses you really need to worry about are those that one might inadvertently pass on to a Windows box. The master server for Tremulous and the majority of the game servers listed therein use port 30720; however, as mentioned above, specific servers also opt to use nonstandard ports. You'll need to allow UDP traffic through all of these, both inbound and outbound.
manpages will not solve all of your problems, but will give you the resources necessary to do so: $ man iptables
If you still aren't comfortable with iptables, Guarddog and Firestarter are the two main apps to help you manage your network traffic in a more user-friendly fashion.