Generally you want to have more space because the images stored on the outside device would need to be encrypted, which may make them bigger than raw binary.
At the same time, it is not very likely that your application will take up all the device space and at the very least there will be some space taken up by the bootloader, so it will not be present in the application images.
Also, if you are not going to implement the protocol yourself, you may want to see what are the requirements in the existing implementations.
But yes, as a first approximation 512 kB is a good size for the external flash.