As usual, the video you posted mixes up how CRTs look with composite artifacts. Games played on a good quality CRT with RGB or component signals (arcade machines, PC monitors, TVs with SCART of YPbPr input) don't look nowhere as fuzzy.
The Megadrive had native RGB output, you just needed the right cable and TV. Maybe that was not common in the US, but it was in Europe; heck, the French model ONLY had RGB output.
All Genesis models were capable of RGB, but almost everyone used the component and/or RF adapter. I own three American genesis models and have yet to ever own a proper RGB adapter for one.
I know, but the world is not only the US. Europe had SCART and pretty much every TV supported it, and Japan had RGB-21 (same connector with different pinout), but I don't know how common it was.
If you have not tried your MD/Genesis with RGB output I would recommend you to try it, the difference in picture quality and clarity is amazing.