I should do a blog post about this or something since people always ask.
I usually recommend people buy used lenses from a place like KEH. Why? A lot of lenses/bodies lose value quickly just from opening the box, and aside from things like AF motors, there's not much that can go wrong with a lens. Small amounts of dust or even scratches will not be noticeable on your images. With wide angle lenses, I'd actually suggest buying new because they hold their value so well. In most cases you would only save ~$50 buying used, so it's not really worth it.
Samyang 14mm ~$300 frequently on sale. Sharp, cheap, and fast f2.8. Quality control isn't stellar, so you might need to return a lens if it's not a good copy.
Tokina 11-16 ~$500. Sharp and fast f2.8. A favorite.
Canon 10-22 ~$600. Great lens, should have been branded L based on its optics. A little slow (f3.5) compared to the others.
Nikon 12-24/10-24 I don't know much about these lenses. I'd probably go with the Tokina over them though.
Nikon 14-24 ~$1000 used $2000 new. Great lens, but Nikon is really gouging on the price. Still, if you have a full frame Nikon, you want this.
Canon 16-35 ~$1500 new. I personally haven't used it, but some have struggled with it, and you shouldn't have to struggle with a $1500 lens. Check out Mike Hollingshead's site for a rundown on this lens, the Samyang 14mm, and a few others.
Canon 14 ~$2200 new. Don't know anyone that owns this, and not sure why you'd spend that much.
Sigma 10-22 ~$400 used/new. Knew a few people with this, no real complaints, but no real stellar reviews.
1. If you want to go dirt cheap: Samyang 14mm
2. If you want to spend a little more, and have zoom capability: Tokina 11-16, or Canon 10-22 if you're shooting Canon.
3. If you want a sweet lens for your Nikon system: Nikon 14-24
4. Ignore my advice, and everyone else's, try out some different lenses, and pick your own favorite
Now if you're mirrorless, things get a little more interesting. You can adapt any of these lenses to your mirrorless body. And more! One of my favorite lenses ever made is the Leica M mount Voigtlander 15mm:
Super sharp, barely any distortion, super tiny. Not too expensive at ~$500. Fuji also makes an amazing 14mm if you like quirky systems.
One of the great things about prime wides is that you don't really need (or want) to focus. Set your camera to manual focus, turn it to infinity, put a rubber band on it, and forget about focusing. Also, don't worry about the speed of the lens. Everyone wants f2.8 and IS, but f4 is only a stop slower. At 10mm you can pretty much shoot 1/10th second exposures without worrying about shake. Use a tripod, bump your ISO a little, and don't be afraid of shooting at f4 or narrower. You'll get sharper corners as well.
The number one most important rule of photography: gear doesn't make the picture, so be happy with the gear you have and take lots of pictures. If you're always wishing for something better your photography will suffer. Hollingshead has an amazing portfolio and some of my favorite shots of his are with the 18-55 kit and the 17-40L - both lenses that aren't known for being amazing.
edit: Case in point, Joshua's post above mine. He has the Sigma 10-20 and loves it. I knew a guy that had a 10-20 and wasn't very happy with it, so he didn't use it very much. Pixel peeping and MTF charts are interesting ways to pass the time, but the best lens for anyone is a lens that they love using.