Beyond If you already have Solus installed and working with the 580, just make sure you're updated before swapping the GPU. You shouldn't have any issues in theory.
EDIT: I managed to totally miss this bit:
Beyond If not, should I install Solus with my 580 and then replace it with the 6600?
This is exactly what you should do, yes. I recently tried to help a friend install on a system with a 6600, and we were unable to get him set up. However, if you start with the 580, install & update, and then swap GPUs, you should be fine.
