Use DDS format textures, these are compressed and load quicker than standard format textures. The other thing with these is that you have a lot of control over mipmaps, which might be very useful. For instance, maybe as planets fade out into the distance you might want to change their colour slightly, to show that being outside of the atmosphere affects lighting etc. I know you said sand box, but your wouldn't fill your sand box with salt just because the consistency is about right.
If you changed the mip maps to be higher contrast at lower resolution for instance, that might be good, like the atmosphere is local to the planet (doh!) so removing it's affect when away from the planet might amplify it. I'm not sure how scientific this would be, or even if your interested in stuff like that - it's just something that you have control over with DDS files is all - I say the same thing to people wanting to automatically fade out foliage on a terrain - DDS files can afford that level of control.
Anyhoo, I would suggest keeping a low res version, load and apply that - but have your big textures load up on the fly. To do this, really your high resolution planet texture needs to be a memblock image, which is as complex as you want it to be. Typically it involves loading in bytes in so many chunks and applying them to bytes in a memblock - then when it's all loaded up you can safely swap your texture with the new memblock image. This would cause a very slight judder - but we are talking about a little delay after loading megabytes of data instead of a 20 second pause!. A 512x512 version for loading and applying instantly is what I would do. Keep that as DDS for maximum benefit, because if you go for a on-the-fly loader, then you can't use DDS, your stuck with using raw data.
It would be good though, very easily you could load up the lower res and use that - then when the game is running it would be loading up these big textures, and applying them to the planets - maybe even keep the lower res version in memory and use a distance check. If a planet is bigger than 256 pixels wide on screen then apply the big texture.
I know you said sand-box, but wouldn't it be great to have it dynamic, like able to handle a planet based on very little information, like a texture map. I would use a folder for each planet, and have a layout like this:
Diffuse.dat :- for the memblock texture, main texture file if you like, raw data.
512.dds :- DirectDrawSurface, mipmapped and 512x512 resolution - for fast displaying at distances over 256 pixels.
Normal.dds :- A normal map for the planet at 512x512 - going full res on the normal map might not be a good idea.
Atmo_sphere.dds :- An alpha-transparent sphere map at 512x512, the planets atmosphere basically.
Atmo_plain.dds :- An alpha-transparent plain texture, to provide atmosphere glows, maybe even cool eclipse effects.
Inbeside the folder, I'd have a little script file to describe the planet, give it a name, a size, plus whatever extra info you might need.
So I'd have lots of planets, each with it's own folder and set of images - some of them wouldn't need suck big textures, or might get by with just the 512x512 image - so individual folders would let you load and apply the relevant files only.
I'd take that standpoint with other aspects like space craft too - even though it's a sand box, it's your sand box and making it easy to add to it increases it's potential no end - like you could provide media very neatly and have it loaded into your project automatically. Maybe the script file can describe where the planet is, and it's orbit, day cycle... if you went all out you could have this script file do everything from name the planet and position it, to determining it's lifespan and mapping it's surface with extra objects.
Anyhoo, I think the lower res texture first, then loading the big one on the fly is the way to go. It opens the door to your own (or established) compression routines too, something to remember if your sand box explodes into a full game project. I can of course help with the on-fly part, maybe should just make a little example of this for you.
