They're one step better than 'buntu, but to be honest I find myself stuck when recommending a decent starter distro these days.
I favour Debian and openSUSE, but neither of those have beginners in mind, and ultimately won't provide a beginner with the most enjoyable experience when first learning Linux.
I do plan on having a good look at multiple distro's, including the writing of installation guides soon, so maybe I'll be impressed with something and be happy enough to recommend something new.
Though that said, its up to the individual as to what distro they use, and we all have different tastes and needs, so its hard to really recommend any distro in particular, as what we deem to be good may not be received as the same by others.
EDIT: You have a good point, 512MB is a bit low for Gnome's DE. Maybe Linux Mint XFCE would be a more suitable choice.