If it were not for the requirement that the prints be on Kodak paper, Samy's Santa Barbara (Dead Link Removed) is a good choice. They provide the cheapest high-quality processing I have ever found, by far. They have the same machines as A and I in Los Angeles, but charge about 5/8 as much for 35mm and 120, and half as much for 220 and sheet film.
I have not found a lab, professional or otherwise, that uses Kodak paper, unless by special request when getting custom optical prints.