I bought my 20mm f3,5 Nikkor-UD back when I still used a D300 as main camera. It was pretty much wide enough for my liking back then, and it happily switched places with my 24mm f2,8 Nikkor-N.C.
Even though I used the two quite a bit, I even started liking them better after buying a D3.
So with all that has been said, I agree with Børge here that a full frame fish eye lens can also be a very nice alternative to a wide angle lens. And with some software, you can effectively defish an image to get something that is close to an image taken with a rectilinear lens. Nowadays on full frame, my 24mm hardly ever comes out of the closet, but the 20mm is with me whenever the 16mm full frame fish eye stays at home.