Yes your are correct the Starter Kit supports voltages between 9V and 12V
The mAh is the amount of current that can be transferred in a certain timeperiod (1 Amp during 1 Hour),
So the more mAh the longer the battery will last.
So based on this you can use one of those rectangular 9V batteries with the kit, but since they only hold around 450 and 500 mAh they will quickly run out of power, thus requiring a higher mAh.
I must also point out that the power consumption will depend on what modules & motors you use,
for example if you have a project that only uses a couple of sensor it will consume less power and the battery will last longer than a full blown robot that uses all sensors and motors