
Shareware
The 'Pro' and 'DJ' versions of this program integrate very tightly with iTunes and an iTunes managed library if you have one. It can play DRM-protected purchased songs and can synchronize playlists, playlist folders, metadata, sound check adjustments and album art with iTunes. It can also match songs with similiar BPM for smooth transitions and can easily handle thousand-song playlists.
The program is definitely designed for a production environment, rather than a live one. It cannot do automatic BPM calculation, but has a little feature where you can 'tap' out the BPM to a song with your mouse/keyboard. And of course you can sort your library or playlist by BPM, or a number of other metrics.
I'm a huge fan of Megaseg, but it suffers from small little usability quirks (the program's insistence on sorting songs with each artist in alphabetical order for instance).

FOSS
This program is gaining a lot of popularity lately. It features some iTunes integration but is quite usable without iTunes and has several integrated organizational devices to make custom playlists or bundles of related songs.
This program is more oriented for a live environment. It has the ability to connect to several USB MIDI controllers and turntables, has automatic BPM analysis, a more robust loop control, and the ability to handle multiple simultaneous sample playback.
Mixxx has the ability to sort songs by BPM or other metrics of your choosing, though I have found it easier to use other programs to manage music libraries. Where AutoDJ and automatic crossfading are integral components of Megaseg, feel like more of an extra feature for Mixxx.