Coulomb's law in electrostatics in analogous with Newtonian gravity. It's pretty clear neither of these can be used in a universe that obeys special relativity. They both must be modified to avoid instantaneous communication (see this question) among other problems. For electromagnetism, we get maxwells equations. For gravity, we have the analogous gravitoelectromagnitism and gravitational waves. However, gravity also causes spacetime curvature.
But what would a "special relativistic" theory of gravity with flat spacetime look like?
Like our universe, Newtonian gravity would still be accurate for describing the solar system. Mercuries orbit would still precess due to special relativity, though maybe at a different rate, it would be the same if we placed a charged test particle in orbit around an electrostatic well at a high speed.
Like our universe, the speed of gravity would equal the speed of light. Gravitational waves would be emitted by orbiting objects and cause the orbits to shrink over time. Since all forms of energy gravitate, the waves would still exert a force on matter, which would change the distance between two mirrors, and thus the waves would still be detectable.
Like in our universe, we still would get gravitational lensing.
Kinetic energy would still contribute to a star-cluster's total gravitational field. Also, an object in a gravity well would contribute less to the gravity felt by a distant observer.
The crucial difference, however, is that "special relativistic gravity" wouldn't have gravitational time dilation. There would be no black holes.
Besides the difficulty in setting up a big-bang/cosmology, what are the fundamental problems with a universe like this? My reasoning is as follows: Suppose an object with mass m resting in a deep gravity well (i.e. the center of a very dense globular cluster) were to convert it's entire mass into a spherical pulse of light (an idealized matter-antimatter reaction), emitting m of energy to a nearby observer. Suppose it fell in from infinity. Since it gave up potential energy V to come to rest in the well, to conserve energy we must have m + E = V, where E is the light energy emitted to infinity. This necessitates gravitational redshift because E < m. Red-shifting without time dilation would mean that distant observers see each photon have less energy but the timing of any light pulses arriving is not slowed down (this is different from redshift in our universe). Although unusual, this doesn't seem to make for an obvious contradiction, it would be analogous to firing ultrarelativistic electrons out of an electrostatic well. Is there a nice argument to show such a universe couldn't exist?