Using numerical techniques and asymptotic expansions we obtain the phase diagram of a paradigmatic model of Coulomb-frustrated phase separation in systems with negative short-range compressibility. The transition from the homogeneous phase to the inhomogeneous phase is generically first order in isotropic three-dimensional systems except for a critical point. Close to the critical point, inhomogeneities are predicted to form a bcc lattice with subsequent transitions to a triangular lattice of rods and a layered structure. Inclusion of a strong anisotropy allows for second- and first-order transition lines joined by a tricritical point.