I've heard a broad range of claims on how large a firewall rule set might be, so I decided to dig around for published data. There are lots of quotes claiming gigantic numbers, but I only found three reports of plausible-looking data collection - one from 2001 and the others from last year. I also have notes from a fourth that I haven't verified.
In practice, firewall rule sets seem to range from 5 rules to over 25,000 rules. Some claim that even larger rule sets may exist.
The number of rules seem to depend heavily on the number of users behind the firewall, and on the firewall's implementation of the rules themselves. If a firewall can create sophisticated rules, then it takes fewer rules to implement the site's policy.
As with everything, small is beautiful. If you have a lot of rules, it's hard to keep them accurate and up to date.