The main thing to being search engine friendly is NOT having redirects. In other words, make sure you are providing me with a link to www.mysite.com instead of www.yoursite.com/oompaloompa.asp?id=1431434817612. Redirects won't count as a backlink to my site, rendering your directory practically worthless. Another good idea is having mod rewrite where your directory structure looks something like this: www.yoursite.com/Computers/Internet/Forums instead of www.yoursite.com/cat.php?id=234. However, mod rewrite isn't as neccesary these days as Google, Yahoo, and MSN seem to have no trouble with the latter type of URL now.
It seems that redirects is ok with most search engines. I found many big directories are using reddirects. Many directory scripts are also designed that way.
good point when you said "big directories", because the bigger you are, the less google penalize you or the less you feel it