Sonic the Hedgehog series had this nailed, also Toejam and Earl had some but that's not NES. The only example I can think of is Super Mario Bros. 3. The zig-zag pattern to black at the end of each level is BIG-TIME Memphis, also the 16x16 icons randomly sprinkled around in the sky, etc, they are getting there. Did we ever have a game that took this any farther than that?
Examples:



