I honestly have no idea about the Mindstorms set. The one my parents bought me is probably 20 years old at this point. I also won a sweet R2D2 one at the mall at the tail end of when I was really playing with them.
Maybe see if there is a set out there that matches one of his favorite fictional characters? Does he tend to favor things with wheels or things that walk when he is playing with toys? (ie would he rather program Wall-E or Iron Man?) Maybe do some basic research and present him with three options? Or maybe start from the "problems" he wants to solve and work with him on building/picking the right robot out. Some questions could be:
- Do you want to walk around the kitchen?
- Would you like to build a track for your car to follow?
- Want to scare your little sibling with a giant scorpion while having plausible deniability? :P
Lego seems to have a huge gallery of bots that people built [here](https://www.lego.com/en-us/mindstorms/gallery). They all may be able to be built with the "default" kit, which I found on [Amazon](http://a.co/15WLhTC).
There are also some great Lego mechanisms books that can be folded into Mindstorms work so it's not just programming, but also mechanical engineering and design. The more integrated it is, IMO, the better, by far.