Definitely do the DMOZ sub but forget about it because like others have said it will take months.
If you can afford it, you should also complete a Yahoo Directory sub. Google still considers Yahoo as a relevant and authoritative site, so such a listing helps you get out of Googles supplemental index sooner.
Speaking of the supplemental index - this is kind of a holding area for new sites (and other sites which may have done something to contravene google's guidelines).
Essentially sites are here because their link popularity (PageRank) has dropped or is otherwise low. Therefore you need quality links to get you out. DMOZ and Yahoo are a good start as are other highly popular directories.
Also, look at who links to your online competitors and see if you can get links back from them as well.