Smaller cells can *potentially* give better efficiency - provided that in the general case you can cull a decent number of them. Otherwise you're left with the overhead of propogating messages through a more complex topology, with no effective benefit from the additional complexity.

If the entirity of your game takes place in open terrain, then using PVS specifically gains you nothing - you are better off simply assuming all neighbouring cells are relevant (always have 9). If however, you have areas that can be occluded from each other, simply shrinking your cell size is not necessarily the best way.

As Steadtler suggested, using variable-size cells is one approach (I prefer a scenegraph style containment approach), which reduces the amount of propogation steps, and the number of relevance/visibility checks, compared to a fine granularity grid-based topology.

The best method of dividing up your game world is usually implied by the game design itself - the typical range of vision, viewpoint, and interactivity that you allow.