The best OS to run on your Lombard is limited not only by the machine itself but by the use that you expect from it. The original MacOS classic will run faster than MacOSX, but that isn't the unique point to consider, and again, it will depend a bit of your previous experience with different OSes and of your expected use.
Maybe you will benefit more from a RAM upgrade than from a faster processor (but think above 400MHz, look for some g3 available upgrade kits, not just replacing the CPU to a 400MHz). I prefer more a stable than a faster machine, so I wouldn't change anything which I not really needed to. These machines were built around 1999, so each one comes with its pre-owned history and present conservation state to take into account (battery, LCD, hd).
I also purchased one Lombard and use it daily since last 5 months. I never had a PPC before to experiment with, so I decided to evaluate and used it like I received, with Panther running on a pbg3 400 w/ 128MB RAM 4GB hd. After some use I upgraded to 256MB RAM and to a faster 60GB hd.
Get installed MacOSX, Yellow Dog Linux, Gentoo and OpenBSD. I didn't like YDL, maybe soon I will replace it with some of DragonFly/FreeBSD/Debian/Ubuntu. Sure each OS deserves its use. I think OpenBSD has the great performance I can extract from my Lombard, depending not only of my MacOSX ignorance but of my use: I use this machine when configuring Linux/*BSD servers (thats my job, no MacOSX server to configure yet ;~).
Working just with unixes, I didn't try the MacOS classic, but think about it.
Hope that helps some lights on the subject.