A cosmic void.
Your best bet would be in a cosmic void. While not entirely empty - they do contain small numbers of galaxies and clouds of gas - they are substantially rarefied compared to your average patch of the universe. Although I've been unable to find concrete numbers for the low-density gas that would permeate a void, we do have estimates for the mean galactic number density, which is roughly $\mathcal{N}\sim0.004\text{ Mpc}^{-3}$, in units of galaxies per cubic megaparsec. If each of these galaxies is the mass of the Milky Way, they contribute a number density of $n\sim0.25\text{ m}^{-3}$ - assuming the galaxies are largely composed of neutral hydrogen.
It seems not unreasonable enough to assume that these galaxies are a decent proxy for the mean void density, and so we can safely assume a particle number density substantially lower than the numbers L.Dutch mentions - by many orders of magnitude!
So let's say you have a cube of hydrogen atoms of side length $l$ with a cross-sectional area $l^2$ of one square meter and the density of water $\rho$, moving at close to the speed of light relative to the gas (which is the worst-case scenario, as it implies a higher collision rate and therefore a higher annihilation rate). Over a time $\tau$, it sweeps up
$$N_a=\tau vl^2n$$
atoms of the void. It is composed of
$$N_c=\rho l^3/m_H$$
atoms itself, and the cube is entirely disintegrated when $N_a=N_c$, or
$$\tau\approx\frac{\rho l^3}{m_Hnvl^2}\approx2.5\times10^{14}\text{ years}$$
If you just want one millimeter shaved away, that should take three orders of magnitude less time - about $\sim10^{11}\text{ years}$.
Over a time $\Delta t$, the cube will pass through
$$N=\Delta t v l^2n$$
atoms, releasing
$$E=N\cdot 2m_Hc^2$$
energy. The power emitted is then
$$P=\frac{E}{\Delta t}=vl^2n\cdot 2m_Hc^2\approx 22.5\text{ milliwatts}$$
which is surprisingly little.
Of course, the whole thing is kinda moot because any void is finite. After all, the Boötes void, for instance, is only 330 million light-years across, and so, traveling at the speed of light, the cube will only spend 330 million years inside, shaving off about 1.3 micrometers in the process. (You can of course increase this time significantly by decreasing your speed!) Your mileage may vary, of course, depending on both the size of your object and whether I actually did the calculations right.
Notes
This is really just a toy model to get you an order-of-magnitude idea of how slowly annihilation will occur. A one cubic meter cube of hydrogen is an unrealistic object and would of course dissipate quickly, regardless of its environment - it's almost certainly not self-gravitating. Therefore, we can't really model the effects the annihilation would have on it. However, a realistic object would indeed see some more complex effects. For instance:
- Some of the emitted byproducts of annihilation (e.g. gamma rays) would be directed inwards, and would potentially ionize or (more likely) knock loose additional atoms of the object.
- The object would likely be slowed down by the drag of traveling through this sort of medium (even such a rarefied one).
- At the (again, unrealistic) relativistic speeds our toy model is moving at, there would indeed be special relativistic effects.
But again, this is just a toy model designed to point out that a cosmic void is an excellent place to set down your antimatter object.
