Check out the Sigma 12-24mm DG (for FF) with Hypersonic AF. I heard that it's a hit/miss depending on the copy, but I bought a used one for $400 and it's been well-used and is tack-sharp. I'm super happy with it.There's two versions of it. The mark II, released in 2011, may be alright (even if it lacks the EX qualification), but the mark I supposedly is not very good, especially for FF. Although, as you say, mileage may vary.
Here's a brand-new one. I'm surprised I got one for $400 (I've never seen them anywhere for that cost) but I'm glad I jumped on it!