The key, for me, to keep lego interesting was to have a lot of generic legos. In my mind, lego has done a disservice to the power of their own invention by focusing more on the lego minifigures and things like bionicles -- which you use to build that one set piece and then don't use much beyond that.
If you focus on the bigger sets and sets of just the standard bricks, the limit is your imagination. In my mind, if you're using instructions, you're doing it wrong.
They still do sometimes—they even have a line where every set has instructions for 3 different models.
On the other hand I used to love making Airfix models.
Things slowly got better with more re-usable pieces until the 2008 a of Matorans, which consisted of 2 feet, 2 hands, 4 limbs, 1 body piece, 1 translucent head, 1 mask, and some combination of single piece weapons - most put together with ball joints.
I personally think this move from technic like "composable" pieces to ball-joint only single purpose pieces was the downfall of Bionicle, but there's probably a thousand other factors involved ;)
Not all kids are different, some will take to Lego like fish to water, others don't care. In my family almost all the kids (girls and boys both) like Lego. This in spite of Lego doing what they can to destroy their image with all the fads an the horrible sets they put out every couple of years until they find their 'true North' again.
To get something approaching the build quality and strength of a lego brick, you're going to need a mighty expensive printer.