It's hard to say, if it's a laptop, I'd go with any of the 'buntus, but if it is a desktop, Fedora is supposed to be good, but I personally don't like it. OpenSuse is good, I tried 11.2 and it was really good at detecting all my hardware.
If they are interested in learning how linux works, I would choose Debian. There is nothing more stable than Lenny IMHO, though it's a bit harder to get everything working.