The exact same way as you'd SEO any website. Get your title, heading, content and text links keyword rich.
Most of the directory has been SEOed by the script itself. What you have to do is get PR7 or higher. Good luck.
Look for link partners, if your directory is a niche type, add meta tags into it. Directory submission is also good for link building.
Do you mean because the recipricol links will build up? I dont really understand this but I agree that paid>free by a longshot unless you want to sort through hundreds of spam links everyday for free.
Yes I mean the reciprocal links will give you higher PR etc... it came out wrong i meant to say Make it a Paid Directory with a Free reciprocal
You might want to try putting articles you wrote on the main page. Maybe turn your main dirctory page into a blog of sorts. I have seen this done a few times and Im sure it helps search engines see your directory in a different light than th e average. Make sure you avoid casino, pharmacy and penis/breast enlargement links. Make sure you dont accept recipricols from link farmish type pages.