I have some old Kodak polymax fiber and RC. They're fogged a bit. Is there any chance they'd work for lith? My only other papers are Ilford which aren't really known for doing much with lith (except maybe for the Art 300, which I do have also). I'm thinking of trying the Moersch easy lith, if the chemistry makes a difference in which papers to consider.
Ilford Warmtone is beautiful in lith, but requires toning afterward, unless you really like an olive green cast to your prints. You get a little bit of grain usually, but it's somewhat dependent on developer dilution and temperature, and can be quite fine grained if you have the right negative (high contrast preferred).
Like Andrew suggests, the Kodak papers might work (I have some Ektalure that is amazing in lith). I seem to remember that the Polymax fiber works with lith, but all you can do is try it out. I have a box of it here that I've been meaning to test, but haven't gotten around to it.
Good luck!