I can see two options that involve what I would consider to be roughly the same level of alteration to physics.
The first is to replace normal inverse-quadratic gravity with gravity that's much stronger, but follows an exponential Yukawa potential. This would result in large structures, like stars and planets, effectively being held together by surface tension, and gravity effectively disappearing once you get a certain fixed critical distance away from any individual body, regardless of its size. The surface gravity of any given body above a minimum critical size would be directly proportional, not to its total mass, but to the density of the surface materials--which means all rocky planets would have approximately the same surface gravity! Perfect for campy space opera. :)
The disadvantages of this system are twofold:
First, there are no orbits. That comes with a silver lining, though, because it means you don't have to worry about drag causing orbits to decay, and planets to fall into their suns. And you don't really need orbits; as long as a planet remains at a fixed distance from its sun, does it really matter if it's orbiting, or just sitting there, inert in space?
Second is that internal pressure is inversely proportional to radius. That means bigger stars actually have a harder time developing enough internal pressure to start fusion than smaller ones, and rocky planets might well have enough internal pressure to fuse iron! So, in addition to fiddling with gravity, you'll want to fiddle with weak and strong nuclear force interactions to make fusion of light elements easier, and fusion of heavy elements harder. I don't know whether or not supernova explosions would be feasible in this sort of universe for distributing heavy elements, but if not, that's OK: dying stars would eventually just cool off and become habitable rocky planets! (Because, remember, surface gravity doesn't depend on total mass--just the density of materials near the surface.) A side benefit of this complication is that hollow worlds become possible, and may even form naturally--if a planet becomes large enough, due to two smaller worlds crashing into each other or whatever, its internal pressure may go low enough to allow the expansion of dissolved gasses in the rock / magma, blowing bubbles in the interior. If you could tunnel into them, you could even walk on the interior surfaces, because gravity is a surface phenomenon, and the Newtonian shell theorem doesn't apply.
The second option is to try to keep gravity the same, and change other stuff to accommodate it.
The problem of all of the air simply collapsing into a black hole is relatively easily solvable; if the air fills the entire cosmos, then no particular patch of it will be able to collapse. The self-gravity of any particular chunk is balance by the gravity of all of the other chunks of space surrounding it. You just need a larger cosmological constant to ensure that space remains reasonably close to flat. So, no changes needed to gravity or any other laws yet.
You do, however, need to figure out how to deal with density variations in the cosmic air background. On the one hand, you don't want density fluctuations to run away and result in local collapses, because if they do, then the background gas will rapidly become segmented into dense stars, separated by space that's been emptied of air... just like out universe. But on the other hand, you do want local collapses of a sort, because you want stars and planets and so on.
That's something of a contradictory situation. The only way I can see to resolve it is to arrange for two different kinds of matter, which can pass through each other with minimal interaction, so that one can be allowed to collapse (forming stars and planets) while the other does not (forming your cosmic atmosphere).
We also need to deal with drag, because orbits are still important in this option. We can solve that problem by positing that whatever material forms the cosmic atmosphere is superfluid--or at least maintains a superfluid state in regions where planets orbit! It's OK if, e.g., stellar heat breaks downs superfluidity at close ranges, or if there are pockets of normal fluid elsewhere out in the galaxy. That way, a planet can move through the cosmic atmosphere with near-zero exchange of energy, and no significant drag.
You could manage by making the cosmic atmosphere out of some variety of dark matter--but that then raises the question of how and why people need to or can breathe it at all! Instead, I propose magnetic monopoles. This universe will have two parallel periodic tables: one of electric elements, like our own, and one of magnetic elements, whose fundamental particles may have other slight differences as well, besides just the nature of their inherent electromagnetic charge, so as to allow mag-hydrogen to condense into a superfluid state at relatively high temperatures.
Most of the time, mag-matter and electro-matter would be able to pass through each without noticing, since there would be no Fermi degeneracy interactions between, e.g., magnetons and electrons. However, just like normal electric atoms and molecules in our universe can have an innate magnetic dipole, magnetic atoms and molecules could also have innate electric dipoles, which allow specific types of mag-atoms and mag-molecules to make dipole bonds with specific types of electro-atoms and electro-molecules. There is thus a clear mechanism for explaining how and why planetary life could end up evolving to make use of cosmically-abundant mag-hydrogen (or some other simply mag-molecule) in its metabolism, despite the fact that most mag-matter passes through most electro-matter as if it weren't even there.
In either case, if the humans in these settings are supposed to be able to breathe the cosmic background air, for metabolic purposes, they would not be breathing oxygen--at least not the oxygen we know from our universe. You will probably also need to handwave minor tweaks to atomic physics to make the air much closer to being perfectly transparent than air is in our world, or sunlight would never make it all the way from a star to a planet! But tweaking biochemistry to give them an inverted hydrogen-breathing metabolism, or something involving exotic mag-molecules, is pretty tame compared to re-inventing basic physics. :)
