I have a LAN of Linux computers that get access to the Internet over NAT. The gateway runs a restrictive firewall. I have ICMP echo requests and replies allowed to pass through the firewall on the gateway, so I can ping any external host from a LAN computer, but mtr and traceroute to an external host hang at the gateway hop.
What additional firewall rules should I have so these tools would work properly?
Linux traceroute uses UDP by default, on a random high port, while Windows tracert uses ICMP. For your Linux machines, you'll either need to configure the firewall to allow UDP on high ports, or use the -I commandline switch to specify the use of ICMP ECHO instead of UDP datagrams.
Edited to add: By default, it picks a random port in the unassigned ports range, commonly referred to as "high ports". Typically this means a port in the 49152–65535 range (see this port list). The man page refers to this as an "unlikely value" for a service to be running on inadvertently, since we don't actually want the host to process the UDP datagrams as information. If you want, you can specify the port with -p, but be aware that it will increment the destination port by 1 with each probe when using UDP. If you want to use a constant port, specify the -U switch (default port is 53 for this). Alternatively, if you don't want to use UDP or ICMP, you can use the -T switch to specify TCP SYN mode, which will use a constant port that you can set with -p. Then you would open that port on your firewall.
Only UDP is allowed for unprivileged users.