Wow, I had no idea that Georello had expanded the product line so much. Pretty cool! I also second Snap Circuits.
Regarding Mindstorms, NXT 2.0 is the latest version. There are other pieces and sets available, but you can do a lot with the base set. It's expensive, but so are 1,000 piece Lego sets.
The instructions really hold your hand. The kit comes preconfigured as an instruction-bot that upon hearing your voice clambers out of the box, explains how to use Mindstorms in a tinny voice, and physically assists you as you reconfigure it into new robot shapes.
That would be neat, and the reality isn't far off. A big glossy insert gets you up and running with minimal trouble. After installing the software that comes with it, you will see
extremely thorough step-by-step assembly manuals for the hardware of several robots. Each sub-assembly is dealt with in a separate subsection; for instance, the head of the gator-bot is built separately. Hooking up each motor or sensor to the CPU is also quite simple, with an RJ-45 (phone) cable that goes to a numbered or lettered port.
In comparison to the more complicated regular (non-Technics) Lego sets, I would say that the pre-designed Mindstorms bots are only slightly more difficult to put together precisely to spec, and that only because the Technics pieces tend to offer fewer up-down cues when you're looking at the directions. It's really not bad, and the directions are very easy to follow.
Regarding the software, it's really not complicated to get started either. I know it might sound complicated, but the Lego designers did a very good job of making it accessible. Mindstorms 2.0 comes with a visual drag-and-drop programming environment. You can, for instance, drag and drop a loop (something which repeats instructions inside itself), drag it bigger, and plop blocks inside of it, each block representing some action. It's hard to explain quickly, but really not hard, even for a child to understand. And all of the pre-designed bots come with their programs pre-written. You can pull up the program and examine and change it at will.
I don't think it is crazy to buy Mindstorms for a five-year-old who likes building a lot. It would probably hold your son's interest for some time to come. I can't answer whether he's ready for it, but perhaps you could find some way to let him play around with a set locally.