Get a macbook pro! (sorry, couldn't resist)
If you do buy one that is over a year old, the discount can go up to 25%, which is a horrible deal for a computer that was released 1-2 years ago.
Personally, if I were going to buy a used model, I'd check out what's available locally on craigslist.
Also, if you're not dead-set on having a brand new machine, you could get a used one on craigslist and save a couple of hundred.
Other than that, the only laptops that I've seen come close have been Sony's, and they tend to be even more expensive.
I've had Asus, Samsung, and Alienware laptops that were built just as well as a Macbook, yet cost a fraction of the price. In addition, the specs exceeded a top of the line Macbook Pro by a longshot. The Asus and the Alienware were really ugly, but the build quality was exceptional.
If I were in the market for an ultrabook, I'd easily pick the Macbook Air. If I wanted a well built desktop replacment, I'd consider the Macbook Pro, but I would also take a look at Asus, Samsung, Lenovo, and even Alienware* before I make my final decision.
On a final note, the specific model if far more important than the brand. Every PC manufacturer has good models and bad models. If you find a specific computer that you like, you should check out as many reviews as you can find on the internet before you buy it.
*I'd stay away from Alienware if you can't handle the hideous design.
I don't see OSX as being an additional cost like Windows - all Macs come with OSX, and it doesn't have to license it from a separate company, like the Dell and Microsoft relationship. The only cost would be $30 every other year for upgrades, but even those are optional.
A refurb definitely wouldn't be a bad option, I have a refurbed iMac and if it didn't come in a brown box saying "Refurbished" I'd have never known. The only thing I will say is that adding a few hundred bucks to your budget for the 3 year warranty is 100% worth it - something breaks, you just schedule an appointment at the Apple store, and they'll take care of it.
The only gotcha is that many of the nice "boot to other OS" features
Use this page: https://wiki.ubuntu.com/MactelSupportTeam/CommunityHelpPages
I decided after awhile, I liked the linux install in a VM instead of a dual boot (Mac OS X is a unix, and the VM on a SSD didn't hurt at all) and wiped it back out.
Historically, Apple charges about 30-70 USD for the OS, so less than the windows OEM license you are paying for on non-Apple hardware
I have no idea if Linux distros work with a completely blank drive, have only dual booted.
I highly recommend a Strata from ZaReason (zareason.com). Unless you're going to be doing a lot of graphics-intensive stuff, definitely go for one with an Intel graphics card, b/c nvidia is a pain on Linux.
I'm assuming you meant to qualify that as NVIDIA's mobile chipsets. Though, I can't say I've had much trouble with them. I've certainly never had much trouble with their desktop products under Linux--I currently dual boot my home desktop between Linux and Windows with an NVIDIA card, and it runs just as well under either (ironically, Minecraft plays more smoothly under Linux...).
Certainly there are some general complaints related to NVIDIA's Linux drivers, but to be completely honest, I've run many NVIDIA cards--including mobile--under a variety of Linux flavors over the years and had few troubles. I even tried installing Arch on an ancient Dell laptop of mine for fun which is equipped with one of the early GeForce Go chipsets, and it still works quite well (KDE4 not so much, but LXDE is perfect); however, it requires installing an older driver.
I'd like to know where you got your information from, because I've run Ubuntu, Gentoo, and Arch all on top of fairly recent NVIDIA hardware. The only relatively minor difficulties I've had have all involved minor tweaks to xorg.conf but even those have greatly diminished in necessity.
As long as I leave my monitor setup as is and don't stir up too much dust, though, it works great.