The best Mac software hands down is called Reunion. I don't know about what is available for PCs (though the ones that get the biggest marketing I understand are not all that great).
One of the best uses the Internet has been put to, and an excellent example of a distributed database, is Gendex [gendex.com] with its millions of records. You will want to be sure that your software can output a Gendex file - Reunion does and I imagine most others do also.
The family tree software I use is Brother's Keeper. You can download the (almost) full version for trial.
In MHO it's the best if you are a serious researcher, and it can also provide eye-candy output if that's what you want. You can have several databases, and it provides good input facilities, and all the reports anone would need.
I have the Windows version. I'm not sure if it runs on Mac.
I have been using FamilyTreeMaker for several years and have been quite happy with it. The current version is version 10, has a lot of features. There is also a free personal ancestral file at Familyseach.org, which I have never used but might be a good starting point.