Canon has three primary grades of lens quality: silver, gold, and red (L-series). The EF 28-135 IS USM is a gold band lens, which generally means it has better build quality, better focus, and usually a bit better optics. The EF-S 18-135 is a silver band lens, which generally means bottom-rung build quality, bottom-rung focus, and basic optics.
In this specific case, the 28-135 has quite a bit better build quality, as its part plastic and part metal,where as the 18-135 is all plastic except the mount. The focus is considerably better on the 28-135 as it has USM (ultrasonic motor) focus, which is smoother and allows FTM (full time manual focus). The 18-135 has a simple gear motor, and does not feature FTM.
Optically, I think these two might be pretty close. The 18-135 has a UD glass element, which is pretty nice for a bottom-rung Canon lens. The 28-135 is decent optically, but its never produced top-notch quality, and has some distortion problems. The UD glass element should help with dispersion (CA), which might produce better corners than the 28-135. Distortion is probably about the same on the two lenses, at least at the wide end. I know the 28-135 is known for a fair bit of corner distortion and vignetting. The EF-S build of the 18-135 might resolve the vignetting problems.
Finally, the 28-135 is an EF mount lens, where as the 18-135 is an EF-S mount lens. The latter will ONLY work on cropped sensor bodies (APS-C sensors). If you ever wanted to upgrade to a full-frame camera like any one of the Canon 5D's or even one of the 1D bodies, you would not be able to use the 18-135 on them.