> When a channel is switched, the TV has to wait for the next I-frame, since P-frames (and B-frames) only encode the difference to the previous I-frame (or to the previous and next I-frame in the case of B-frames).

You can apply the encoded difference to a grey (or black!) screen, the way (IIRC) VLC does in such cases. This means that the user immediately gets a hint of what's happening onscreen, especially since the audio can start playing immediately (also, often the P/B-frames replace a large portion of the on-screen content as people move around, etc.). Surely it isn't any worse than analog TV "snow".

If it looks too weird for the average user, make it an "advanced" option - 'quick' channel changes or something.