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.