I know this is quite an old post, but I stumbled across this and just thought I'd pitch in my two cents worth...
I have been using Linux for quite a few years now, and have gone through a number of different systems (both laptops and desktops). Some computers I've bought for personal use, others have been issued to me by my employer.
I agree fully with the two posts above - Intel is definitely the way to go for Linux. The Intel HD graphics driver is open source, and is included with the Linux kernel (which means you don't have to go to the effort of installing a binary proprietary driver from the manufacturer - which can be quite a daunting task on Linux the first few times).
The last AMD/ATI graphics cards I had were two 7780's. One was running on a AMD A8 motherboard, the other on an Intel i5 motherboard. Both had dual monitors - one 2560x1440, the other 1920x1080. While they "kind of" worked, they never worked satisfactorily. There were tearing issues, wobbly windows were not smooth (constant judder and lagginess), overscan issues etc etc etc. The end-user experience sucked.
I heard a lot of good things about the nVidia drivers with Linux, so I spent the money on two GTX 660TI cards and used these to replae the 7780's. While the 660TI did work exceptionally well in single monitor mode, it struggled running two monitors. There was always tearing on the second monitor, things got juddery/janky if playing a movie etc.
With Ubuntu 14.04 (running the 3.13 kernel), things are much better with nVidia and multiple high resolution monitors. Everything is almost perfect (I'm using the proprietary nVidia 331.67 driver). I say "almost", because when I stream video from my NAS box using the default video player, things because jerky/laggy (with wobbly windows enabled, you really notice it when you drag a window around while the video is playing). This does not occur if playing the video in VLC player instead (so perhaps something to do with hardware acceleration/decoding).
I've had the most satisfaction with the Intel HD on-chip GPUs. Every laptop I've owned with Intel HD graphics has run Linux beautifully. Even with the Intel HD 4000 in my Chronos 7, driving two monitors (the second running at 2560x1440) isn't a problem. Even when I steam video using the default video player, things are still smooth, fluid and snappy (it passes the wobbly windows test with flying colors :)).
As an experiment, I decided to rip out the 660TI from my Intel desktop machine and try the onboard Intel HD 4400. It worked extremely well, even with two monitors, although there was no convenient GUI to fix the overscan on the second monitor (I messed around with xrandr, but still wasn't able to completely get rid of the overscan). The other issue I had is the maximum resolution. The motherboard has a HDMI port and a DVI port - neither of which is capable of driving a 2560x1440 monitor (even though the box was stamped with "Ultra HD 4K", which is false advertising as far as I'm concerned). My laptops have DisplayPort or Thunderbolt ports, so they have no problem driving higher resolution monitors.
For a single monitor machine running Linux, I'd stick with Intel HD. If you want to drive multiple monitors, just be aware there's no easy way (i.e. a GUI) to deal with overscan. If you want to drive monitors higher than 1920x1080, then just make sure your motherboard comes with a port capable of of higher-than-HD output (DisplayPort and Thunderbolt will drive 2560x1600, and probably higher).