If you are familiar with Debian, you might just want to go with it again. It has (some / a few / lots of) improvements since "way back when".
Ubuntu is based on Debian, and is very popular, according to the DistroWatch site (
http://distrowatch.com/ ), and also judging by it's hot forum activity. It, like Debian, uses a GNOME gui. If you prefer KDE, which is more Windows-like, Kubuntu is the same product except with KDE instead of GNOME.
Others that work nice out of the "box" are Mandriva, PCLinuxOS, Mepis, Fedora Core, and probably some others I will get flamed about for not mentioning. I just mentioned the ones I have used myself.
Almost any box can run Linux if it has standard hardware. The things you need to watch out for are any uncommon pieces, or anything that is newer than the distro you want to use. I wouldn't worry about getting Linux pre-installed unless you don't already have access to a computer that can download and burn iso cd's. By installing yourself, you can try several different distros until you find the one that works best for you.
One thing you might try is to find a used Windows XP computer that some poor schmuck abandoned when he had to get new hardware to run Vista.