Okay, as mentioned, I took my time tonight to look why X is so much faster with the Yocto image compared to Debian, and I think I found the reason.
First, I changed the Debian installation to use the driver "omap" instead of fbdev and copied the configuration over from the Yocto rootfs.
That sped things up a bit and made xrandr usable, but it was still slower then on Yocto.
With xrandr I could switch the resolution to 1280x720 and even 640x480, but it didn't increase the speed. Moving windows around was still stuttery, so it doesn't seem like a memory / bandwidth issue.
Checking /var/log/Xorg.0.log revealed what the real issue is:
On Debian, there is only the basic omap driver installed. It lacks DRI, DRI2 and PVR2D / XV drivers from TI. It clearly says it in the logfile ("XV not initialized" "Couldn't load submodule omap_pvr", etc.)
On the Yocto, it successfully initializes XV, DRI2, etc.
Unfortunately, Yocto uses X 1.11 and Debian 1.15, so I couldn't copy over the modules for testing.
It means however, that the slowness comes from missing OMAP driver modules, so we'd need to include them.
Seems like there's an Ubuntu Package: https://gitorious.org/ubuntu-omap/pvr-omap5/source/7b9f231fb44c03bc02f42b6bb...
There's also a prebuilt-OMAP5-Debian-Image available: http://elinux.org/BeagleBoardDebian#OMAP5432_uEVM
Haven't checked whether they have the drivers included or not though.