I have tried 3 papers so far, always with Kodalith. For another choice, I have read that some people like the Moersch lith developer. Here is a link to a store in Toronto that sells it. Call them and see if they can send it down to the US:
Regarding papers that respond to lith, Ilford MGIV FB gives the most subtle results. It is probably a useful choice when you want to tame a very contrasty neg but don't want/need too obvious a lith effect.
Forte Polywarmtone FB (Variable Contrast) responds to lith more noticeably. Personally, I don't like the warmtone brownish-cast it has but others seem to like it.
My preference so far is for Luminos Classic (Warm tone) Fibre. I believe it is also known as Kentmere Kentona is the UK and Australia. This turns a colour that people have described variously as peachy/pinkish/reddish. However, a few of my friends have thought the prints were sepia toned. Of the three papers, this one is supposed to have the most interesting response to toning after development although I have yet to experiment with this.
For references, Tim Rudman's "The Master Photographer's Lith Printing Course" is an excellent and comprehensive guide. Les McLean wrote a superb 4 part series on lith printing in Black & White Photography magazine. In February 2003 (part 2 of the series) he discusses different papers.
I will try to upload a few photos to my personal gallery shortly so you can see what the papers look like when developed in lith. I don't have any scans of the Forte Polywarmtone though. If you have any other questions about lith printing, feel free to contact me and I'll try to help.