The buffer-then-debuffer technique can work well with tiny buffers. As discussed, if you can see the result the buffer is too large. However, even a tiny buffer will degrade the original data to some extent.
A possibly better alternative is to use 'Fill holes' from the Processing toolbox after your dissolve. It is like 'Delete holes' except here you have some control over the size of hole you wish to fill (and so can thereby retain large lakes like Lake Malawi for instance).
Another option would be to download the land boundaries from the Physical 10m data set in Natural Earth and then intersect that with the Admin0 boundary lines from the cultural data. The lines are single lines so shouldn't have the issue of in exact polygon boundaries. This won't work well for island, but you could generate polygons from the lines.
Yet another option would be to do the dissolve and buffer operation as before but then difference the result against the oceans dataset. The Oceans data is the inverse of the land. As the buffer operation will tend to fill in coastal 'wiggles', differencing against the ocean (or indeed, clipping with the land - see link above) should correct the coastline back to how it was.
Finally you could go old-school and using GRASS tools in the Processing tool box, you could clean and build topology (v.clean and v.clean.advanced) and set the snapping tolerance (something small initially) before you do your dissolve operation. Having 'grown-up' with ArcInfo 6.x, I'd be inclined to go old-school. Good topology makes for happy geographers.
