We apply First-principles calculations to study the structure and the relative stability of several stoichiometric and nonstoichiometric boron nitride fullerenes of sizes ranging from 28 to 128 atoms. Among the structures considered, we observe an overall tendency for the formation of octahedrally faceted shapes as the atomic number increases, with more spherical shapes being prevalent only for small nonstoichiometric cages. From these observations, we expect that experimentally observed BN fullerenes of diameters of similar to 12 Angstrom or larger to be polyhedrally faceted regardless of their stoichiometry. We also address the relative stability of the fullerenes in both nitrogen-rich and boron-rich environments. For the smaller molecules, we find that the stoichiometric B16N16 is more stable than the nonstoichiometric structures with similar dimensions, in both environments. For the larger sizes, the nonstoichiometric B32N36 and B60N64 are found to be more stable than their stoichiometric counterparts in a nitrogen-rich environment, while the stoichiometric structures are the most stable under boron-rich conditions. These conclusions remain largely unchanged, when we consider the gas-phase limit of atomic reservoirs.