Binary bismuth chalcogenides Bi2Se3, Bi2Te3, and related materials are currently being extensively investigated as the reference topological insulators (TIs) due to their simple surface-state band dispersion (single Dirac cone) and relatively large bulk band gaps. Nanostructures of TIs are of particular interest as an increased surface-to-volume ratio enhances the contribution of surfaces states, meaning they are promising candidates for potential device applications. So far, the vast majority of research efforts have focused on the low-energy (0001) surfaces, which correspond to natural cleavage planes in these layered materials. However, the surfaces of low-dimensional nanostructures (nanoplatelets, nanowires, nanoribbons) inevitably involve higher-index facets. We perform a systematic ab initio investigation of the surfaces of bismuth chalcogenide TI nanostructures characterized by different crystallographic orientations, atomic structures and stoichiometric compositions. We find several stable terminations of high-index surfaces, which can be realized at different values of the chemical potential of one of the constituent elements. For the uniquely defined stoichiometric termination, the topological Dirac fermion states are shown to be strongly anisotropic with a clear dependence of Fermi velocities and spin polarization on the surface orientation. Self-doping effects and the presence of topologically trivial mid-gap states are found to characterize the non-stoichiometric surfaces. The results of our study pave the way towards experimental control of topologically protected surface states in bismuth chalcogenide nanostructures.