I've have the 18-55 and had the 18-135. I had both at the same time for quite a while, but eventually sold the 18-135.
I've also got the Tamron 17-70mm but for some reason can't bring myself to sell the 18-55. It's a great little lens for general use, especially as a travel lens due to it's size.
The Sigma is apparently a bit sharper, but it's worth noting that it doesn't have OIS. I can tell you from my experience with the Tamron that the constant f2.8 is not as big a deal as you think it will be.
I had the 18-135 for a while as it's particularly good for IR photography. When i went to Scotland in January, I took pretty much all my gear and despite having a selection of very good lenses, the 18-135 was on my camera 90% of the time. In the changing weather i didn't want to be changing lenses too often, and the focal length range is surprisingly versatile. Sure, optically it isn't a patch on the primes, but it is certainly more than good enough for the convenience it brings to the table.
Personally, I've always discounted the Sigma because my body lacks IBIS. Given your options, I'd probably go with the 18-55 unless you really need weather sealing. It's a good middle ground of quality and utility, with the Sigma leaning more on quality, and the 18-135 bringing more utility.