Excellent points ROQ!
That first gig...always the hardest! Have a few demos in hand, business cards, and start hitting the pavement. Talk to bar/club managers, explain what you are looking to do, and how you are different from the other 1,000 DJs he just interviewed (without bashing your bretheren DJs, mind you). Start with smaller venues/bars first. You might even have to take a weekday gig to get your foot in the door. Be persistent, but not desperate. With some bars, you might have to provide an entire sound/light system, so be prepared for that.
Good luck!!
Bill