Up front, I'll address the last question. This is a long piece, but you might want to familiarize yourself with it. It's legendary anyway.
Linux is not Windows.
IMO, the only reasons to avoid Linux are these:
1) You are addicted to high-end games. If you're still using '98, I doubt that's the case.
2) You have some need for specific, proprietary software that you need to run at maximum efficiency with no professional technical support, e.g. a CAD system.
3) You aren't willing to learn a new way of doing things.
The last element is usually the show stopper for most folks. Linux is different. There's a lot of layered stuff on top of it to help the transition from Windows, but the bottom line is they are not they same (thank gopod), and they won't be. This is often what throws people. There will be a learning curve.
The physical building of a computer for Linux is no different than one for Windows. The only real thing you need to watch out for is hardware that isn't supported for Linux, which isn't a great lot these days really. In fact, Linux tends to deal with older hardware better than Windows does 'cause drivers are sometimes hard to find for those older things.
If you're thinking of building new from scratch, it's fairly simple as far as the base system is concerned. Motherboard, CPU, hard drive, optical drive, graphics card ... it's actually difficult to find one that doesn't work with Linux now.
The challenge is sometimes in the peripherals, e.g. wireless networking, printers, scanners, etc. My general strategy there is to go to NewEgg or some similar place and search reviews of hardware for the word "Linux" and see what has been said. Naturally that strategy works better for products that have lots of reviews. And, with all of it, if you're not afraid of looking for an answer in the Internet wilderness, you'll generally find a solution.
My advice for a gift would be to decide on a distribution for a beginner system. For that I'd suggest either
Ubuntu,
SuSE, or
Mandriva. They'll all work, and I suggest them because of the vastness of documentation and online support groups for newbies as well as printed books that deal with them. (There's also Fedora/Red Hat, but I have had show-stopper problems with it and so don't recommend it to those new to Linux.) Then, order the disc/box set from the organization that distributes it. Note that you
don't have to do this; you can just download it and burn it to a disc. But for a gift, it's nice for aesthetic reasons since the disc is customized. Plus, at least with SuSE, you can get a book.
Then, get the most recent version of the
Linux Bible. It has reference material and lots of information for several different distros (SuSE, Ubuntu, et al are Linux distributions or distros).
Some websites:
http://distrowatch.com/http://www.linuxhardware.org/http://www.linuxquestions.org/http://www.linuxhelp.net/Intro to Linux This is for the more hands-on stuff and is generally not distro-specific, e.g. basic Linux commands and such.
Hope that helps.