I highly recommend the all-grain 1 gallon kits from Brooklyn Brew Shop:
http://brooklynbrewshop.com/beer-making-kitsThis was what got me started homebrewing 3 years ago. Since then I've brewed over 300 gallons of beer and have upgraded to a 5 gallon and then 10 gallon all-grain system.
The reason I recommend these kits is that they are easy and they deliver a high quality beer that is as good as anything you can buy from a craft brewery.
I wouldn't recommend getting something "fancier" since they might not like doing it or might be overwhelmed by the complexity (brewing doesn't have to be complex but home brewers like to make it complex). I left my kit in the cupboard for 6 months until my wife finally said - "if you aren't going to brew it then I will!". Little did she realize that that first batch would create a brewing monster.