I'd suggest going with bloated Fedora, and stripping it to the core. And I'm not quite sure if trying to fit it on a 512MB stick is reasonable; USB sticks are so cheap nowadays that it seems reasonable to get a bit bigger one and save yourself hours of hassle. Time is money. :)
