The main component of complexity is the codec standard itself. As Stefan Seidel already mentioned, MPEG-1 is probably the easiest to encode and decode. MPEG-2 should also be relatively easy to handle. But your video will be huge if you want a decent quality.
MPEG-4 and H.264 add a bit of complexity here. One of the most important (and widely used) features here are B frames. Here, the a frame of the video can depend on multiple frames that were shown before or might be shown later. This means: More computation needed, more memory needed, more disk access.
So, if you're encoding your video, make sure to disable B-pictures. In H.264 this can be achieved by sticking to the Baseline profile (e.g. in FFmpeg with
-profile:v baseline). The baseline profile was included in order to support faster encoding and playback devices with low processing capabilities (such as mobile phones).
In any case, your result depends on how your operating system delegates the decoding tasks. If it's just using the CPU, stick to the "simple" codecs. If it's using the GPU, you should be fine to use H.264.
Certain players like VLC may use the GPU for decoding video, but this is not guaranteed and heavily depends on your OS and the graphics card. I recommend simply doing a few tests with different codecs. The fact that you're using a screensaver and not a dedicated player may very well change your results too, so don't rely on testing with, e.g. VLC.