Did you try iDevGames.com? They have a few sprite sets for space games, I believe.
Actually, Coldstone supports PICT, JPG, PNG, and BMP - not GIF. You don't want to use JPG for anything besides stills, though, as its lossy compression will mess up any transparency.
Each frame of an animation (sprite, etc) needs to be a separate file in your Coldstone "Pictures" folder. You can use a subfolder of "Pictures" if you like, and it helps to have all frames of a particular animation in the same folder, though it isn't strictly necessary.
If you use PICT or BMP for your sprites, they use simple white masking - any part of the image that is pure white will be transparent, and any part that isn't, won't be. This simple method takes the place of a separate mask file as used by EV*. As with EV/EVO, this masking method will give your sprites pixelly edges.
If you want smooth antialiased edges as in EVN, you need use PNG files, which have a built-in alpha mask (again, no need for a separate file.) There's been plenty of discussion about alpha masking and PNGs around here, so try searching this board
------------------
I would rather discover a single fact, even a small one, than debate the great issues at length without discovering anything at all. - Galileo Galilei