We report the detection of sixteen binary systems from the Anglo-Australian Planet Search. Solutions to the radial velocity data indicate that the stars have companions orbiting with a wide range of masses, eccentricities and periods. Three of the systems potentially contain brown-dwarf companions while another two have eccentricities that place them in the extreme upper tail of the eccentricity distribution for binaries with periods less than 1000 d. For periods up to 12 years, the distribution of our stellar companion masses is fairly flat, mirroring that seen in other radial velocity surveys, and contrasts sharply with the current distribution of candidate planetary masses, which rises strongly below 10MJ. When looking at a larger sample of binaries that have FGK star primaries as a function of the primary star metallicity, we find that the distribution maintains a binary fraction of ~43$±$4% between -1.0 to +0.6 dex in metallicity. This is in stark contrast to the giant exoplanet distribution. This result is in good agreement with binary formation models that invoke fragmentation of a collapsing giant molecular cloud, suggesting this is the dominant formation mechanism for close binaries and not fragmentation of the primary star's remnant proto-planetary disk. ; Comment: 42 pages, 11 figures, and 3 tables. Accepted for publication in MNRAS