Why do different batteries of the same voltage have different results and which battery would i choose?
The PP3 Energizer battery has lithium-based chemistry, which usually have much higher discharge rate than other types (alkaline) of small 9V batteries. And yes, it is related to the difference in internal resistance. However, even with the same chemistry, the internal design of a battery might differ between manufacturers and battery design target. Apparently your homemade robot has pretty high demands for current.

As long as your MCU controller has a regulated internal power, and the 9.6V input doesn't exceed its input limit, your arduino won't be damaged.

Regarding the particular battery and particular charger, they appear to be completely compatible, since the charger has user-selectable charge rate. You just need to select the right current to your battery of choice.