I also am content to go with what's available, and what I can make myself.
The old Portriga was a great paper. I've seen prints on Velour Black and lament never having tried it myself. I've got some Haloid Industro, but it's gotten a bit foggy--still useful for some things though.
If you're looking for the classics currently available, try Azo, J&C Exposition graded, Efke PL100, FP4+, TXP, J&C Classic 400. There's some really nice stuff out there.
Get some amidol. Azo and J&C Exposition (Efke Emaks) look great in amidol.