Check out LEGO Mindstorms, it's basically LEGO with motors that you program. I think something physical attached to the (abstract) programs would be a great way to start.
It's recommended for ages 10+, but I'm sure a bright kid with an adult helping would love it.
Check out Not Quite C (NQC). It lets you write actual code to run on the Mindstorms platform. (This was my first experience coding.) http://bricxcc.sourceforge.net/nqc/
Well, personally I always had a fascination with software but not (yet) with hardware. Mindstorms sounds a bit like hardware... so I don't think it would have necessarily worked for me. YMMV.
It's recommended for ages 10+, but I'm sure a bright kid with an adult helping would love it.