We serve as a service provider to other agencies. We don't know what network device they have; how they set it up... We have Cisco Firewalls that need to be set up. It's very hard for us to set base rules on the firewall. We don't what to filter out packets that are needed for other agencies but we want security!
Please don't be offended, but this question raised my concern level quite a bit. It seems there is a lack of a fundamental process to determine the integration with other agencies, and that will hinder any proper configuration of the firewall. The good thing is you recognize that security is important and that you are trying to find the balance between restricting needed services and not restricting unneeded services. This process can be defined from some of the points hinted at in your question. Before you can effectively configure your firewall you need information from those you are providing service to. So here's my suggestion at how to quickly go about gathering the information. After that you'll need to determine if there are interoperability issues with the agencies, and looks for holes in the rules that create a greater risk exposure. Let's start with the information.
First, decide what is the appropriate base configuration for you alone. The normal strategy of denying all and then explicitly opening what is needed should be followed. Document the requirements and the resulting configuration.
Second, you need to develop a short list of questions for each agency to determine what it is they need, in other words, what are their requirements for you to provide. This may be difficult if the agency doesn't have good technical people, or any technical staff at all. So be prepared to not only ask questions like "will you need https, and will you need ftp?", but to go further when you see blank stares and ask "Will you require secure web for transactions, and will you be moving files?". The point here is to narrow down their requirements to a simple list to base a configuration on. You should also ask what equipment they have, and for configuration information that may be important concerning their equipment (what if they use an unusual port for a service?).
The next part is to evaluate the implications of adding the agency's required configuration to your configuration. Will it expose you in ways that are unacceptable? Are there other conflicts with your or other agencies' requirements? This part of the process is really a paper review of the firewall configuration changes, and is part of a change control process. Mentioning change control seems to some as excessive, but realize that changes to the firewall need to be tightly controlled and evaluated carefully. While the firewall should not be your only security device, to most it is the major cornerstone of their security infrastructure. Establishing a clear method to review, approve and implement changes will save many problems later. Once your configuration file gets to be quite long, it will take you longer to re-construct why each rule is there, so it is easier to begin with a clear, documented process. Also if you loose an agency, you can easily backtrack and remove the parts of the configuration that relate to that agency, helping you to simplify and clean your configuration.
While you may have been looking for a quick set of rules when asking your question, the issue is how to develop the configuration process. I hope this has provided guidance and been of help.