Firewall

а это зависит.
общее универсальное правило: подрубить все, что очевидно, все остальное отрубить, чтоб в логи шло. если чего работать не будет - смотрим в логи и подрубаем.
если есть маскарад, то с высоких на высокие всем общаться

Как быть с программами которые создают динамические порты?

о каких программах речь? клиентских? если да, то юзаем stateful firewall,
каким есть netfilter/iptables:

iptables -A INPUT -i $EXT_IF -p tcp -m state --state ESTABLISHED,RELATED -j ACCEPT
$EXT_IF - имя внешнего сетевого интерфейса,
для '-p udp' - то же самое, но там понятие connection state весьма расплывчато...