McVittie spacetimes embed the vacuum Schwarzschild(-(anti) de Sitter) spacetime in an isotropic, Friedmann-Lemacetre-Robertson-Walker (FLRW) background universe. The global structure of such spacetimes is well understood when the FLRW background is spatially flat. In this paper, we study the global structure of McVittie spacetimes with spatially non-flat FLRW backgrounds. We derive some basic results on the metric, curvature and matter content of these spacetimes and provide a representation of the metric that makes the study of their global properties possible. In the closed case, we find that at each instant of time, the spacetime is confined to a region bounded by a (positive) minimum and a maximum area radius, and is bounded either to the future or to the past by a scalar curvature singularity. This allowed region only exists when the background scale factor is above a certain minimum, and so is bounded away from the Big Bang singularity, as in the flat case. In the open case, the situation is different, and we focus mainly on this case. In K < 0 McVittie spacetimes, radial null geodesics originate in finite affine time in the past at a boundary formed by the union of the Big Bang singularity of the FLRW background and a hypersurface (of varying causal character) which is non-singular in the sense of scalar curvature. Furthermore, in the case of eternally expanding open universes with Lambda >= 0, we prove that black holes are ubiquitous: ingoing radial null geodesics extend in finite affine time to a hypersurface that forms the boundary of the region from which photons can escape to future null infinity. We determine the structure of the conformal diagrams that can arise in the open case. Finally, we revisit the black hole interpretation of McVittie spacetimes in the spatially flat case, and show that this interpretation holds also in the case of a vanishing cosmological constant, contrary to a previous claim of ours.