I think that it's not effective as it used to be, so I wouldn't pour all the resources onto that.
Relevant ones are definitely better, free ones are better (because they are free) than ordinary paid ones but not as good as the very popular ones (paid or free).
Make also sure that they are not going to go out of business soon for whatever reason (choose established ones) and that they are do follow and seo friendly in general.
Submitting just for traffic doesn't give enough benefits, you want traffic, PR (if you need it) and SEO links.
Find preselected and updated lists, DIY is better and change descriptions, titles and categories if you can. Categories should be as accurate and precise as possible.
Avoid featured link options, unless it's something extraordinary, and reciprocate links only if you have to and the directory is relevant.