I'd probably go with 2GB as 4GB and more seems more like Windows 7 territory to me.
Frankly, depending on what mobo and CPU the system is build around, 1GB and even 512MB will work fine until you start using software that outgrows the configuration.
If you (for whatever reason) want to use 512MB and something like a Pentium 3, stay with SP1 and perhaps SP2 at the most and use NLite or similar to slim down the install. Also tweaking the OS can make it run more snappy. I mean it will work but if you want easy mode with WinXP and performance just get something as recent as you can get away with.
So tldr: Get 2GB. 1GB will also work and you can use 512MB if you want to put it on a Pentium 3 or something.
My experience has been putting WinXP on systems like Pentium 3 1000MHz with 512MB SDRAM and a usual mechanical harddrive.
Later on I've installed XP on progressively faster systems, leaving the slower systems using WinME instead of XP.
Athlon XP and Northwood (especially >2GHz Northwoods) are basically WinXP territory and especially if you use lots of RAM and a relatively fast harddrive.
But it's really a matter of preference. WinXP will work on slower systems like Pentium 3, but it won't be as much as a speeddemon like if you put it on a Core2Duo with 4GB DDR3 or something.