I would recommend first thing, to make absolutely sure which program you are going to want to use first. Granted, it makes more sense when you have a controller in front of you to do all the tricks and truly show what's possible with each software, but the software I beleive is the first thing to nail down. There are a lot of choices these days, the top two I in my mind are Traktor and ableton, but there are others that can acheive the same product, like mixmeister fusion, dj decks, PCDJ, mixvibes, and a whole slew of others.
I say program first, because you will have to have a foundation to base your controller needs on. Secondly, you will also know the limitations of the program so you will have an idea of what other expenses might come up, ie other controllers, midi translators, extra vst's. You can always expand your foundation later, but it's good to know if you're going to need jogwheels for Traktor with manual beat matching, or if you would like endless encoders because you will be controlling 10+ channels in Ableton. This will save you some money and frustration of trying to adapt a controller to your specific software needs instead of having the closest match to what you're trying to accomplish.
Also, make sure that you know the basics of the mapping procedures for each software and each controller you look at, because some are far superior to others and allow you to do more without a midi translator or other software.
Bookmarks