I am familiar with Horowitz and Hill, and think that it is too advanced for what I am looking for. Granted I do not see my nephew that often. I think Art of Electronics would be great in a few years if he is actually interested in electronics. I would like to get a copy for myself someday, too.
At this point the top contenders are "make: electronics", and Forest Mim's book "getting started in electronics." I looked online and saw that Radio Shack carries them both, and stopped by a store today that actually had them on the shelf. The main problem with Mim's book is the handwritten nature and old-school feel may make it hard to convince a modern day teenager to give it a fair shot.
I think I will skip the spring-loaded kit thing altogether, and simply place a Mouser order for a breadboard and the components to go along with whatever book I get. The kits are either very expensive for the nicer ones that have breadboards in them or look much too juvenile. Also, the prices on parts from a regular seller like Mouser are waaaay less than radio shack.
I must say that it is embarrassing that I am not familiar with these kinds of books - all my degrees were in EE! However, I didn't actually learn anything about circuits until sophomore year. It was electromagnetics, not circuits, that got me into EE.
Jason