The Tokina mentioned, and also the Sigma 10-20 f/3.5, are both excellent, and possibly had for $500 used. The Sigma 10-20 f/4-5.6 is a little softer and a little more distorted, but quite affordable, even new.
I've tried the Sigma 10-20mm and own a Tamron 10-24mm and I think the Tamron is best when it comes to landscape. Used versions sell for 325-400 on eBay which is a very good price in my opinion for the quality it gives in return.
I've heard good things about the Tokina 11-16mm but haven't tried it yet. It costs $600+ though.