What is a surprise is that if you reject UDP packets for SSH, it still works, but the login process slows down massivley; taking perhaps 15 seconds. Apparently while SSH uses TCP for its primary business, some of the alternative automatic authentication steps like DSA-keys try using UDP, and you have to wait for them to time out before it just simply asks for your password. It's a really subtle error, so maybe it's worth a hint.
If you want to do see this in action, first enable remote login, turn on your firewall, and in a Terminal window, type the following:
sudo ipfw add 4943 deny udp from any to any in
Then go to another (modern) machine and try to login to the Mac using ssh.
WARNING: If you simply delete the firewall rule, the Mac will behave normally, except that it will not allow you to use the GUI firewall tool in system preferences until you reboot. Rebooting also deletes the above rule as well, so you don't actually have to delete it yourself. But if you should want to delete it by hand without rebooting, just type this in the Terminal:
sudo ipfw delete 4943
[robg adds: I haven't tested this apparent slowdown ... this previous hint covered another SSH slowdown and fix.]

