Heterostructures involving graphene and bismuth, with their ability to absorb light over a very wide energy range, are of interest for engineering next-generation opto-electronics. Critical to the technological application of such heterostructures is an understanding of the underlying physics governing their properties. Here, using first-principles calculations, we study the interfacial interactions between graphene and bismuth thin-films. Our study reveals non-intuitive phenomena associated with the moiré-physics of these superlattices. We show a preservation of graphene-derived Dirac cones in spite of proximity to a substrate with large spin-orbit coupling, a greater influence of graphene on the electronic structure properties of bismuth, and the surprising presence of a magnetic solution, only slightly higher in energy (by several meV) than the non-magnetic structure, possibly validating experiments. Such subtle and unanticipated phenomena associated with the moiré-physics are expected to play key roles in the practical applications of heterogeneous assemblies of two-dimensional quantum systems.