Debian stable (used to be the most stable one from what I know)

RHEL5.4 of course.

Thisara asked for a free Linux so RHEL can't be suggested. Maybe CentOS (it's a Red Hat rebuilt) could be a good choice or Debian stable as suggested by ryuslash. Ubuntu server is based on Debian and could be a valid solution. My suggestion is to install the distribution that you are most familiar with.

Who said you can't get RHEL for free? support and RHN cost money, Linux is free

Actually I disagree with your sentence.
Linux isn't always free and RHEL is not free (intended as gratis). You can install it (if you find cds) but without a subscription it's almost useless (you don't have the access to their repositories and so you can't use yum, pirut and pup). Linux is always open (in fact even RH gives you the permit to access their sources), not free. Here there's an interesting discussion about it.
It's not always simple to understand that "free'' is short for "freedom'': the usual explanation of the meaning in this environment is the famous sentence of R. M. Stallmann "free as free speech, not free beer". Those interested in reading advocacy pieces for open source software and free software should see http://www.opensource.org and http://www.fsf.org.

yep, centOS is a free rebuild of RHEL but its a crap choice for a server (peoplke say its great - read on to see why i disagree)

1) No support. if you are running a misssion-critical business system, its worth it to pay for the support

2) The lag in patch-time.

When RedHat discover a vulnerability, they announce it and release a patch. It takes Centos 1-7 days to release thier own version. In that time, you could be hacked.

I say RHEL, SLES or if you want a low-cost solution, debian.

I agree with the statements about CentOS, the lag time is a bit excessive recently due to the whole power struggle in the organization. Ubuntu is a good choice, but if you are going to use it for a server, use the LTS (Long term support) release. 8.04 was an LTS and I believe 9.10 is going to be an LTS (Not sure on the specifics of that though). The normal Ubuntu lifespan is only about 6 months, but the LTS releases are supported for 2 years.

I'd say Debian, as it is very stable compared to ubuntu, as other distrobutions.

I know you asked for a linux OS but why not FreeBSD? I'm setting up my own server and i was adviced to use it as an excellent choice for my purpose.