I use to DJ a bit for friends on parties using Virtual DJ. Since the last release (3.2) it supports hardware accelerated playback of MPEG-2 and normal playback of AVI files. Its beat detection algo is very good, I even managed to beatmatch without headphones with just a little shift I corrected while second track was in background. There are some nice internal visual plugins and just yesterday developers released a freeframe wrapper. It supports alot internal audio plugins + VST plugins. Did not try if you can control VST and freeframe by midi but internal plugs can.
Great tool for one-man-armys.
Some skins made for AVDJing (what a word..)
http://www.virtualdj.com