I think we should start by being able to create backgrounds like they did for Bear in the Big Blue House. They were able to use more colors at once by changing the palettes every two scan lines.
Also, there's the DK Land trilogy, where the VRAM is updated every frame to allow for more complex sprite animation. These two functionalities should theoretically be added before attempting to utilize full-motion video, wouldn't you say?