I had the 10-22mm Canon lens for my 40D. It's a common wide-angle zoom lens, equivalent in angle of view to a 16-35mm lens on a full-frame camera like the 5D. Now, at the widest end it's really wide - MUCH wider than the 28mm you have as your widest focal length right now. But the range is actually pretty good for you -- you'd have 10-22 and 28-135 covered, with no overlap and not much missing in the middle. My 10-22 made very high quality images, though like most WA zooms it suffered from some softness in the corners.
A really wide lens like this requires some care in use. Just pointing it at a distant scene and zooming out to the widest setting results in unsatisfying images. Finding an interesting foreground and juxtaposing foreground/background can provide a great feeling of depth. (The attached photo was made at 10mm on a 40D.) It takes some effort and work to use well and get the best results.
Another lens that I could recommend (perhaps more strongly) is the Canon 15-85. This is an EF-S lens, so it's made for your 50D, and it covers a focal range from a solid wide angle (24mm equivalent) to a nice short telephoto (135mm equivalent.) It's a great general purpose and landscape lens, has image stabilization, and the widest focal length is a little more manageable than the 10mm. I use a 24-105/4 on my 5D, and this is the logical equivalent for the smaller-sensor cameras.
EDIT: Another option is the Sigma 12-24mm lens. It's a full-frame lens, so it can be used on your 50D, where it will be a very wide lens, but it can also be used on a full frame camera, where it is a really, really wide lens. I have one at work, and use it on both kinds of cameras. Image quality is excellent -- it's my architecture lens. For me it's best used on a tripod, at f/11, mirror locked up, carefully focused with live view (standard careful landscape and architecture technique.)