Just to report back in on my testing...
First, fixing the libGL.so message doesn't make the ugly triangles go away, but it seems to improve things a little overall, including general performance. Apparently, Celestia can run without whatever it was looking for, but runs better when it finds it. No surprise there, really.
Next, the triangle problem is less annoying when you make the view window very large, at least the center of the window is usually pretty clean then.
Also, the Basic/Multitexture Render option has no noticeable effect on the triangles.
I haven't tried the configuration option suggested by Selden, I will do that soon and report back, since I don't see anyone else piping up about it.
And finally... I can also confirm that swapping out the ATI for a GeForce FX 5200 cures the problem, not that anyone has any doubt
Cheers,
Jay