Thank you for using the Support Forum. I appreciate you sharing your experiences with paper. Paper is very important for the print quality and proper function of the printer. I am sure many will find this information useful.
While it helps to have a capable printer to produce good results, paper choice is a significant factor in the overall equation. I realize that "good results" is subjective, so what I am about to share is based on my simple expectations. My typical requirements break down into two scenarios: Routine printouts and Finished output. The former represents over 95% of my activity, while the latter encompasses less than 5% of my activity. So for my expectations, it came down to two kinds of paper to fulfill nearly all of my printing needs. Next is what I ended up choosing.
For routine prints I chose Hammermill's 24lb Laser Print. It's a very smooth paper that produces crisp results. This paper is bright with a consistent texture that causes the output to jump off the page with pronounced contrast while not distracting your eye with blotchy background noise.
My finished output largely involves images; some of my sources are old black-and-white photos. I spent a fair amount of time evaluating several different sample sheets (from Red River Paper) to arrive at my choices. Yes, to my surprise, I ended up arriving at two choices for this activity instead of just one. While Red River Paper focuses on ink jet paper, a number of their offerings produced outstanding results from the 8580. Their 60lb Polar Matte produced incredibly smooth solid colors, superb detail, and high degree of opacity (for 2-sided prints). The 68lb Ultrapro Satin 4.0 excelled with black-and-white photos, producing very minimal noise, especially in dark regions of a print.
These three choices of paper have enabled me to extract the most from my ColorQube's potential. I am very pleased with the results! Perhaps this may help some of you arrive at a similar conclusion.
Finally, here are some paper-related links that I found to be informative: