You should be able to pick up an 18mm 2.8 for less than a grand. Adorama has one used for $850. If you don't mind MF, there are quite a few Nikon options wider and cheaper than that.
There's a Sigma 12-24 4.5-56 for $859. No idea if it's a good lens though.

Check Sigma 15-30 f3.5-4.5, arround $300 used

I have had mixed experience with ultra wides (for me, that means 20mm and down...) on the D700. The 20/2.8AIS works reasonably well from about 2 stops down from max aperture. The nice/cute little 20/3.5AIS does not really do it for me. Pretty soft in corners it seems below about f/8 or even 11. I recently got a mint 18mm/3.5 AIS for under 500, and I am pretty impressed so far. Still manageable size. If you find 24mm a useful length, as I do, I cannot recommend the 24mm/2.8 AIS highly enough! An amazing bargain (available in great shape for ~200), nice and compact, and perfectly matched with the D700. Very good performance at f/4, excellent by 5.6... The D700 corrects the modest chromatic aberration perfectly. I go nowhere without the 24, and currently choose the 18 to go with it, if I need wider.

How about the 12-24mm Sigma? That is a lens I like very much and it is full frame as well.

Albert,
20mm on FX format cameras is impressively wide.

I use a D700. I agree with you when you point out that Nikon perhaps has a shortfall of wide angle lens choice for FX bodies (i.e. no "mid priced" wide zoom)

I have tried 3 wide angle options for my D700. I did purchase a 2nd hand AF Sigma 14mm f/3.5 prime. Whilst the field of view was amazing, the soft corners ate too far into the middle of the frame for my liking and it does not take filters out the front. I sold this lens.

I also have the 20mm f/3.5 AI prime lens which does exhibit slightly softened corners on the D700 but I find them mostly quite acceptible for in the field short to mid distance landscape / botanical habitat type photography. This lens is the one to have if want to shoot directly into the sun without hideous flares and it's comparitively cheap so I'm keeping mine.

I also use most often the Nikon 17-35mm AF-S zoom which as you know is costly but to me represents best value and performance for landscape shooting as it's optics are excellent and it takes filters. You might consider a 2nd hand copy if you can find one for sale.

I return to my initial statement, 20mm is very wide on a D700. I love panoramic / sweeping vast open landscapes but do not often go wider than 20mm, even on my 17-35mm zoom.

Matthew,

I agree that, in practice, 20mm is very wide, and almost always wide enough on FX. I also love the 20/3.5AIS for its size---no bigger than a small normal lens. If one is going to do a lot of wide angle work, however, my 20/2.8AIS seems to be better, especially for landscape. Actually, I got the 20/3.5 largely to replace my 2.8 in a smaller package. But, I have decided to keep both for now. I will not be surprised, however, if my new (to me) 18/3.5 convinces me that there is no advantage left to the 20/2.8. The 18 is not much bigger. Even though it, too, has somewhat soft corners at the widest apertures, the D700 has so much effective resolution that one can afford to crop a bit and still produce large prints (easily 13x19 or so). In practice, the 18mm performs just as well on D700 as the 20/2.8, just with a few more degrees of 'room'.

I have never been particularly interested in the HUGE 17-35 zoom, even though it is probably excellent. I much prefer small prime lenses, and have yet to see a zoom that does not represent a compromise in quality. One near/possible exception is the great 12-24/4.0 Nikon zoom on DX. Even there, however, my 24/2.8AIS outperforms the zoom on DX at the same aperture. I find even the 12-24 large and clunky, and I now rarely use it. (I rarely use DX anymore at all... and almost exclusively use a combo of D700 + film body such as FE/F3/F4/FM3a, or a rangefinder.)

One interesting observation I made about my 20/2.8AIS, however, was that it performs very badly on my D200 (probably worse than the 20/3.5). Not sure why. It just is soft over a large part of the frame until f/11 at least... Not sure what the problem is, as the D200 otherwise performs well, and the 20/2.8 does quite well on film and FX...

If 20mm is OK for you, I warmly recomend Sigma 20mm f1.8 which is really a state-of-the-art piece of glass. The only "bad" thing is that it use 82mm filters...

I use the 18-35 f3.5-4.5 on FX. It's a little soft in the corners wide open but I usually shoot it at f8 where it gets pretty good. I think I paid around $450 about 5 years ago.

There are two affordable choices in ultra wide zoom lenses for FX. Ian mentioned Sigma's 12-24mm. I use this lens and it is an incredible lens for the money - about $750. The other is Nikon's 18-35mm Although not quite as wide as the Sigma lens, it can be purchased used for under $400.

Nikon also makes a 14mm lens but you will pay well over $1000 your $1000 budget for it. Tamron offers their SP AF14mm F/2.8 lens for about $800.

If you really want ultra wide, the Sigma is the way to go.