It depends on how much of a budget you have. For example, if you could spend $1500 with no regrets, I'd get one of
these and a boxed set of the latest version of Red Hat (~$40). Then you'd dual boot RedHat and a version of Windows that came with it (RedHat does that automatically) and then you would have a great gaming computer with Linux and Windows all at the same time... But, if you are pretty expierienced with computer hardware and setting them up (hardware wise), then you could build your own computer. Also, I'd reccommend
newegg for parts, and then you could buy a boxed set or download a Linux distro and install it...
But as far as I know I wouldn't reccommend systems with Linux pre-installed because they'd overcharge you for labor and software, stuff like that. Also, the first time I ever used Linux I had Red Hat and I installed it without a glitch; highly reccommended for newbies to the Linux world.
Oh yea, I left this out: the computers at the site you provided a link for had Pentium IIII processors, but I have one with one of those and another one with an "AMD Athalon 1800+" and the one with the AMD runs faster than the one with the Pentium. Also, it has an "integrated" LAN controller, and that means that you can never get a new one without buying an entire new motherboard, but if your computer isn't on a LAN that wouldn't matter.