How do you determine the best Linux server distro is for a company? Or are they all mostly the same?

It depends entirely on what the server is expected to do.

If you are looking for a stable and secure platform for services that are to be exposed to the internet you may choose one platform, if you are looking for something that easily integrates with a windows environment and has lots of pretty widgets for administration you may choose another.

A great deal of it comes down to the personal taste of the administrator, what type of package management system (RPM, Deb, Pkg, etc) he prefers, and what type of start up scriptsdirectory structures he’s confortable with.

Ultimately most of the major linux distributions have something unique and desirable to offer (otherwise they wouldn’t be around for too long).

One other thing that may influence the decision is the need for commercial applications, you are more likely to use one of the “big box” flavors if you need Oracle or other business software support.

Finally, it depends on the size of the support staff at the company in question and how heavily they will need to lean on the support (or lack thereof) provided by the software distributor.