@Nigel_Aves -
Not sure if you are talking about colorbox or galleriffic. You need to find the right balance of theme options and uploaded image sizes.
If you are talking about colorbox: There is a setting in the theme options to have colorbox target either the full original image or the default sized one. If you choose the default sized option, you can set the size in the top core theme options, then pre-cache them all using the pre-cache backend options.
If you are talking about galleriffic: You can try adjusting the theme option - "how many images to pre-load". The reason you may be getting a big delay, but then it is fine is because you have too many images pre-loading (try reducing that number).
You also may want to look at the size of the images you are uploading. Large images take longer for the server to process and cache.
Of course, as acrylian says, if you visit all your albums once and cycle through the images, everything will then be pre-cached for your visitors.
Again, you need to find an acceptable balance between these user controlled options.