FWIW, it works well with a fairly typical "allow all out, deny all in" firewall configuration. That is what I have set up on my server, and it works fine.
If you go the deny all out, yeah, you'll probably have to set up more specific outgoing exceptions for Mosh.