I would highly recommend the microbit driven cutebot. You can use block based programming which I find is much easier to get kids started on. There is even a Scratch interface for microbit, if you want to start a little slower. A new version of the microbit is coming out in November. You can do quite a lot with the new version see https://news.ycombinator.com/item?id=24763120
The micro:bit itself is the ideal "physical thing that is controlled by your code" and it is indeed very fun. The cutebot is a great place to start but you might want to consider getting some other bits and pieces too. There are all kinds of breakout boards that will provide servo control, relays, etc, and any of those would multiply the fun you can have. Maybe browse some of the prebuilt kits to get some ideas.
The micro:bit also has a built-in radio. It can do Bluetooth Low Energy, but it can also do a micro:bit specific protocol that's easier to use and less memory hungry. So getting two micro:bits opens up a whole bunch more opportunities, too. Last weekend, for example, we turned the cutebot into a remote control car by using the accelerometer in the second microbit to create a wireless steering wheel.