Disclosure: I work for Linode.
360 MB is a fair amount of memory, but it's nothing to phone home over when it comes to LAMP stacks. You need to be fully aware of ways to optimize your stack in this amount of space; a 64-bit OS will directly impede those efforts by using more memory overhead for some things. Knowing each of the distributions you listed like the back of my hand (I built a couple of them), you are really best off going with Ubuntu.
I run Debian on jedsmith.org and Ubuntu on my development Linodes, and they're probably the most efficient of the lot; Ubuntu, being the current forerunner of distributions, will get you everything you want -- security, performance, and a big community to answer questions.
Great opinions from cletus:
I'm half-tempted to suggest Arch Linux just for a barebones distro where you only install what you need as unnecessary packages can eat up your memory really quickly.
I've heard the same about Arch as well, but haven't tried it. Another Linode employee, Sam, swears by Arch and has lots of good things to say about it.
Also, re: LAMP stack, consider using nginx instead of Apache for better performance on a low end VPS slice.
jedsmith.org is nginx in front of FastCGI PHP, and it screams like hell.