I started with Epson Matte paper (EEM, now called something else), and learned how to get the most from my printer with just on paper. I wanted to cut down on the variables.
Then I bought some sample packs from Inkjetart.com. They come with one or two sheets of 8-12 different papers, marked with a label on the back. You can test a lot of very nice, expensive papers that way without buying a whole box. I printed the same image on each paper, and compared them.
(As an aside, it's amazing how bad EEM looks against some of the other matte papers. It's almost yellow in side-by-side comparison.)
I happen to like a lustre finish paper, too, and tested a sample pack of that style. I ended up buying 50 sheets of 17x25-inch paper of the Inkjetart house brand, which is about half the price of Epson lustre, and available in the larger size. (Epson papers come as 17x22.)
So the sample packs worked pretty well for me.