As you have already found, they are more similar than they are different.
One of the most conclusive pieces of information on the comparison between the two can be found in the review of the EF-S 18-135 lens at the-digital-picture:
While its focal length range is shorter than the 18-200's, the 18-135 is less expensive and has image quality that is similar or slightly better in sharpness and distortion.
I would take a look at the reviews of both lenses to see which one might fit your style and price range better:
It is anybody's guess why Canon introduced both lenses in back to back years 2008/2009. I would guess that the price difference is the main factor that many people are considering. The 18-200 is around $600 USD, and the 18-135 is around $350 - so it is quite a difference for most people. I would consider which one fits your budget, and purchase accordingly.
This is a direct comparison of the IQ of both lenses wide open at 18mm: the-digital-picture.com
As others have pointed out in comments, other options may be better, such as purchasing a 70-200mm f/4 non IS, or maybe a 50mm f/1.8. The options are endless, but I'll keep this answer just focusing on what you are specifically asking.
Conclusion
To me, the 18-135mm is a bit better IQ at a lower price point, so if I was only looking at these two lenses, I would go with the 18-135mm.