Joel,

The end-all-be all of printing for long-life use is pigment printing. However, it may take an iteration or three with a service that provides such a service before you get tonal balance you're happy with. My recommendation would be to make a 3 x 3 grid of the same shot and print that grid at 8x10 or 11x17 or some such. Then in PS modify the color and intensity balance slightly on each sector and use the grid to suggest what the final print should be.

The printer will dictate the paper. Generally low-acid rag is a good starting point.

Myself? I'd use this as an excuse to buy myself a pigment printer... but that's just me...