If you want the maximum performance boost for the least amount of recompiling, then recompile the kernel and/or libc; these are used my most programs across the board and so should make the most noticeable difference.
Originally Posted by TheStarLion
I could also, in theory, move to x86_64, as the processor supports it. With less than 4GB of RAM on the system though, is it really worth it?
It depends on what you're doing, but it's generally still not a good idea to use 64-bit executables on systems with less that 4GB of RAM, unless you're doing something that would significantly benefit from a specific 64-bit extension, or run mathematical programs that use a lot of 64-bit variables (astronomical simulations spring to mind).
The problem is that your data variables get aligned on 8-byte (64-bit) boundaries instead of 4-byte, resulting in a lot of wasted memory space between variables. In turn, this means you're using memory less efficiently, and have less memory to use as a cache space, resulting in more direct disk I/O. This tends to wipe out any performance gain you get just from moving larger numbers around. Because you have less free memory, you may even find your system swapping more quickly, which very quickly causes performance problems. So I'd stick to 32-bit if I were you.
Hope that helps,
—Robert J Lee