This depends on how the sprite is going to be rendered, as well as what you are going to do with them when you render them.
If you are going to avoid scaling the sprites, making them the same as their final rendered resolution as possible will help keep the quality higher. I would definitely stick to power of two texture sizes, since it does seem to help in general.
However, if you're going to be doing a lot of transformations on your sprites, particularly with rotations or scaling, you may want to go slightly larger than the resolution they will render, since the resampling may be slightly better quality. You'll want to consider how many sprites are being composited and displayed at any time, and what hardware you'll be running on (xbox, pc, both?), to determine the best options for balancing performance with texture quality.
If you're not going too crazy with the number of sprites, though, you can probably go at a higher quality, and allow the system to downsize them as needed, and get good results.