I don't know if any TurboGrafX16 games suffered from this problem, but they were not fundamentally immune. Any game pushing the limits of a console in this era could have lag frames, even if the limits are higher. A bug could cause it even in a game that doesn't come anywhere near to pushing the limits. A NES with a faster CPU could potentially fix the lag frames in Super Mario Bros but it would likely cause compatibility problems with a wide range of games.
The explanation for the lag frame is actually not that complex. Console games of the pre-3D era were all tightly synchronized to the TV screen refresh rate. Games needed to fully update the display in a single screen refresh (1/60th of a second on NTSC consoles, 1/50th of a second on PAL consoles). If took longer than this then the game would display the same frame for twice as long as normal (or more if it took even longer), but the game's internal logic would behave as if only a single frame had elapsed. So if Mario was moving across the screen at the rate of one pixel every frame, a lag frame would cause Mario to stop moving for one frame. In a second he would move 59 pixels across the screen instead of the 60 he should have, assuming an NTSC console and just one lag frame.
Every 1/60th of a second (1/50th PALs) the console would start the process outputting a frame to the TV. This process would end with the vertical retrace, where the CRT beam would be turned off and moved back up to the top of the screen. At this time games would read the player's controller and update the display as necessary. Normally most games wouldn't have to do much to update the display, just move a few sprites, and change a few tiles. On most consoles, the Atari 2600 a notable exception, the actual output of the display was handled in the background by the graphics chip. After updating the display, the game program would simply wait until the next vertical refresh.
Pseudo-code for the logic of most games looks like this:
while not game_over:
wait_for_vertical_retrace()
read_controller()
update_display()
If updating the display took so long that the vertical retrace happened during the update then the game would simply not notice. The game logic would assume the update_display
code was being called after each and every vertical trace.
I don't know what would cause Super Mario Bros to sometimes take longer than normal to update the display. Normally games try to finish updating the screen by the time the vertical retrace reaches the top in order to prevent tearing, leaving a lot of extra time left over. It could be that there's a lot that needs updating, or it maybe its unpacking graphic or audio data from ROM into RAM. It could just a bug that causes something to take much longer than it should. Given that the lag frames you mention appear to be the result of glitches exploited by speed runners, it's probably the later.