Compile everything on your system, from glibc to XFree86, to the kernel itself, with gcc/g++ 3.2. That way you can -O3 optimize everything (some people say this causes problems with segfaults with some programs -- I've never seen it happen, so either it's the hardware, or I'm just lucky), and, since it's the newest gcc, you can use the newer -march options. I've got an Athlon XP in my main machine, so I built an LFS system with gcc 3.2, and used -O3 -march=athlon-xp -mmmx -msse -mfpmath=sse on just about everything.
Even just with gcc 2.95.3, and -march=i686 (which is what I was using the first time I built an LFS system), I saw a couple of hundred extra FPS'es on glxgears, when I moved from Mandrake to LFS. Mandrake had everything compiled for i586, which was OK for compatibility, but was horrible for speed.
If Debian compiles everything for i386 (which I don't remember for sure -- they might), then you'll see even more of a speedup if you were to go to a source-based distro like either LFS or Gentoo or whatever.
But you have to compile everything, otherwise you won't get all of the advantage. If XFree86, for example, is still compiled with only medium optimization for a 386, everything graphical is going to be slower.
And a lot of source-based distros (like LFS) aren't all that great at a few things, like package management. Gentoo is reportedly pretty good at this, with its portage/emerge system, approaching what apt-get can do, but I've never actually tried it.
Just a couple of ideas anyway.