Don't bother listening to some other people recommending a MacBook of some variety if you really want to run Linux on it. As someone else mentioned, I've never gotten Linux working on it and not have it heat up to crazy levels with the fans running constantly. The multitouch features of the trackpad don't work and so on.
Your best nearest bet is a Thinkpad. Be sure to DDG (DuckDuckGo) the particular model you're looking at to get a jist of other people's experiences running Linux on it.
An old X200 here and Ubuntu runs great.
+1 for the user who suggested a used Mac. I've recommended them that option to a few friends, no one has ever regretted it.
As far as quality goes, I'm still using a 4 year old Macbook (not even a pro) on a daily basis. Still very relevant with a 2.4 GHz Core 2 Duo and 4 GB ram.
I have already dropped mine from the table and flooded the keyboard with an entire glass of diet soda.
If I am out working with other people I always smile when people start putting their macbooks into special protective sleeves and what not. I just take mine and throw it into my bag.
-screen size (any preference toward matte or glossy?)
-weight
-CPU and video card
-battery life
-cost
I would suggest you look at HP EliteBooks and Lenovo ThinkPads. For instance, a ThinkPad W510 or EliteBook 8540w.
I personally own an HP EliteBook 8540p.
-2.53 gHz i5 CPU
-NVIDIA NVS 5100m (equivalent to the GeForce 330m)
-15" matte 1600x900 resolution (quality comparable MacBook: http://www.notebookreview.com/default.asp?newsID=5881&p=...)
-4-5 hour battery life, although I'm still using the original battery
-built like an absolute tank
I got it off of eBay for $600 last summer. The models I mentioned above can have 1080p configurations, and I know for a fact that the 8540w has the DreamColor configuration, which is about the best display you can have in a laptop; they're quite rare, however.
You'd probably have trouble picking up brand-new, refreshed models for under $1000, but that would be the same case for a MacBook.
For example, I am writing this on a T500, which does have a single-touch trackpad, but it is also 4 years old. Its successor (the T510), as well as the present model (the T520) both have multi-touch touchpads. If you have experience with an older model of ThinkPad and are trying to compare it to the current generation of Apple laptops, I would argue that you do not have enough data to make a comparison.
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.
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.
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.
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.
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.