When I buy a Linux Computer I focus on network, processor/RAM, harddisk.
Linux is a networking operating system, it is great for all things network, make sure the ethernet is 1000Mbps (usually called 1Gethernet). You may not have 1Gpbs Ethernet routed today but you will.
Linux does not require ultra-fast processors but you want to pick something that is x86 processor based with 64-bit architecture (AMD-Athlon64 or Intel-Pentium) and a relatively common motherboard so support for peripherals is not an issue.
Memory is cheap, 2GB RAM.
Harddisk: SATA is the nascent technology, SATA-I=1.5Gbps, SATA-II=3.0Gbps(max)
I am not particularly concerned about the video card since I always run VNC. I only need the Video Card for boot and initial installation. I then move the Linux Box into a closet with excellent network access and run everything remotely. I can do this from anywhere on the planet.
That all said, you could dust off an old PC from a few years ago and install Debian/FedoraCore/Ubuntu/...
It will work great with the older hardware. That is were Linux/GNU shines. It doesn't need but can use a 256MB Graphics Processor just to run like Vista. It doesn't need but can use 2GB RAM. It doesn't need but can use 750GB Harddrive.
I scavenge 2-3 year old PC at work and load Linux/GNU on them creating a server farm.
I just need AC power and an 100Mbps Ethernet Connection and I am good to go.