My neighbor, the Fire Department, has put up a chainlink fence and gate along our shared property line. It divides my backyard and their parking lot. Their parking lot is not fenced on the other side - it is adjacent to the main street. They're telling me I can't go through the gate to get out of my yard, that it's their gate and I can't use it. I thought the fire department was a public access place. Anyone can walk through their parking lot, park their car there, meet friends, whatever, but I can't go through the gate to get out of my yard. Is this right?
The fire department is entirely within its rights, which are the same as any other property owner. The fact that property is owned by a governmental body does not mean that members of the public can't be excluded that property.
Some governmental property is public, but lots of it is private, and this would usually include most parts of fire department property. As long as you have not been denied any access to a public road by this fence, there is nothing improper about it.
Anyone can walk through their parking lot, park their car there, meet friends, whatever,
This is almost surely inaccurate. The fire department does not have to allow members of the public to have any access to their property and probably would demand that most of the uses you describe stop if they interfered in any way with the performance of its duties.