Yes, I can see similar behaviour on my system, too, but apparently with some differences.
(My system here is KDE on Ubuntu, but without using Compiz, and I should mention that the graphics subsystem is particularly slow, because my PC does not have a graphics card, but uses on-board graphics (by ATI), which is fast enough for everyday desktop tasks, but can be noticeably slow when it comes to fullscreen graphics or video (with the exception of playing DVDs with VLC).
When playing a tape with ">>>" (warp forward mode), large screen sizes (or fullscreen) also massively slow down playback speed, while a window size of 100 % makes things very fast.
The main difference here is that I have around 70% CPU usage of the R'n'D process when running in 100 % window mode, while I have only around 10 % CPU usage when the R'n'D window has full screen size, most probably because the CPU has to wait for the slow graphics subsystem most of the time.
It should be noted that all drawing functions work on a 100 % window sized bitmap buffer in system memory (which puts all the load on the CPU), then copies that bitmap to a texture of the same size (still without scaling) and finally renders that texture to the screen (including all neccessary scaling), so all scaling should be done in video memory.
The interesting part seems to be that using Compiz to zoom into the window still seems to be fast on your system, so it looks like all of R'n'D's drawing is not done by the graphics card, but by the CPU (while Compiz zooming the correctly uses the graphics card, which is as fast as it should be). Not sure what the SDL library is doing in your case, but it seems like it is doing everything in system memory instead of using the graphics card for the scaling part.
Unfortunately, I do not have a test system with reasonably fast graphics anywhere around, so I cannot test this case.
BTW: Which setting for "special rendering" (setup->graphics) are you using? I've done the above tests with the default mode "double ...", but I have more or less similar results with the other rendering modes here.