Even pumpkin toadlets, who famously can't coordinate their landings, the problem isn't the size of their brain, it's their vestibular system.

I'm of the opinion that most animals are probably a lot higher up the sentience scale than is the current social consensus, but I don't think exercise is itself a major cognitive effort. Arbitrary games sure (not just the rules, anything social involves modelling multiple entities like yourself), but not the physical exercise itself.