If you're shooting landscapes, you're on a tripod, or at least a monopod most of the time, correct? Then you can generally use a longer shutter speed to avoid higher ISOs, and a mix of open and stopped down.
If you don't have a good quality tripod, and you mostly shoot landscapes, I'd actually invest in a high quality tripod first. It'll cost you as much as some mid priced lenses, but if you select the right one you can use it for years and it will help with your landscapes a lot when it comes to fine detail. Just stop down (higher f-number) your lens to around 6.3-8 which generally increases the lens sharpness by a good bit on nearly all lenses.
If you have a pretty decent tripod, then it's time to look for a lens. Do you want ultra-wide? Or is wide to normal going to be good enough? And do you think you'll move up to full-frame (FF) camera like the 6D or 5d3 in the future? For ultra-wide, there's really only a few options for crop-sensors, but they tend to be decent to good optically. You can get ultra-wide FF lenses that will work on your 500d, but they'll function as wide to normal focal length lenses.
Frankly, one of the cheapest lenses you can get is actually quite sharp. The Canon EF-40mm f/2.8 is quite sharp even wide open, and stopped down improves some. It's also only $200, I think $150 right now after the coupon/rebate that Canon is offering. It'll be in the normal focal range (~64mm effective field of view) on your camera, but it's quite cheap, and a great deal.
If you want wider, the new Sigma 35mm f/1.4 for $900 is very good optically, although it'll be ~56mm FoV for you which is still normal. Next is really looking at the Canon 24/28mm lenses, with the 24L f/1.4 probably being among the better, although still quite expensive. Then there's the Canon 17-40 and 16-35 zooms. The 17-40 might be quite good for you since it gives you ~28-64mm FoV, while avoiding the extreme corners where it tends to be quite soft. It's also relatively inexpensive, $839 ($739 right now after rebate) and pretty good optically, except for extreme corners which on a crop you won't have. The 16-35 v2 is a good bit better in the corners, and a lot more expensive. From what I know, both are quite good optically stopped down, although the 16-35 is still the better.