It really depends on how wide you want to go and how much you hate switching lenses. I'd say that purely from a focal length coverage and image quality viewpoint, the
EF-S 15-85/3.5-5.6 IS USM would seem to be your best option, though at around $735 it's not inexpensive. The advantages of the
E-FS 18-135/3.5-5.6 IS are that it's less than 1/2 the price and you wouldn't have to swap lenses so often. It's not quite as wide, but that might not really matter much to you since it will be a lot wider than your current 28-135 is. I'm not sure you'd see much difference in sharpness though. With the 28-135 you have a full frame lens, so you're only using the center part of the image and that will tend to give you better edge and corner quality. With the EF-S 18-135 you're using all the image circle of the lens, which only covers a crop sensor.