Which is more important in your opinion...quality of interconnect between pre-amp and amp or CD player and pre-amp? Basically, which should I replace first? Thanks for your thoughts.

I'd go for the pre/pro to amp first simply because that would benifit all sources , not just the disc player.

Sure - that's why between preamp and power amp is also the best place to put a tube buffer: all sources get the benefit.

I'd replace the longer cables first. The longer a cable is, the more you'll notice a difference in the quality. On a cable of three feet or less, you may not notice any difference at all, although I do use upgrade cables for all my interconnects over the grade that typically comes "free" with a component. I've read some sources that say you won't notice a difference in any cable under six feet, which is probably why I haven't noticed sonic differences in cables. I have had setups where 12-foot cables were needed, but my latest setup uses nothing over six feet (to the dual subs). Most cables are only three feet. For me, the major improvement in cables is the quality of connectors that usually have a more precision fit to the component jacks (although I have experienced brands that fit so tight they need pliers to get on and off and I fear for breaking the jacks whenever I need to change cables).