I've seen Mixxx seems to be one of the few that's not proprietary, but I'm having a hard time choosing what to at least start out with What choice are there? What are some of their strengths and weaknesses?
VDJ is mostly the industry standard and is extremely easy to use. It has almost every feature you could want, its customizable with different skins, and easy to find your way around.
TRAKTOR PRO is the new benchmark in DJ software. Mix digital files on four decks, using the high-quality internal mixer or external hardware, and the best effects suite around. Fully primed for professional use, TRAKTOR PRO redefines the art of DJing.
The downside, it costs money...
The major players seem to be Serato, Traktor, and Virtual DJ. I hear a lot of people like Mixxx and Deckadence, although they don't seem to have quite the user base.
There's also Ableton Live if you don't necessarily want to use something that looks like turntables. It's sort of a fundamentally different way of DJing though. It's like having a giant looper instead of decks.
This is like asking Windows vs Mac. Both have their pros and cons and their fanbase is also strong.
The best way would be to find what DJ software is ideal for a specific requirement.
Personally I can find all major features in Traktor pro and this list has good comparison of all major DJ software.