If I have an image of 800 by 600 then should the random crop still be 256 by 256 or is there a formula for deciding the size of random crop based on original image dimensions?
There is no formula but you should consider the size of the object in the original image.
As you may imagine you need to catch enough info to be useful