I have not seen dependencies or dependency types effect performance, through 13.1.
The number of assignments can have a big impact on performance, though I'm seeing significant improvement with MSP2010 and Windows 7 64 bit - expect it would help further with MSP2010 64-bit. I have an example project where the number of assignments is over 500,000 actual hours - takes about 12 minutes to open from CA PPM into MSP. I can still find ways to kill this output (not completed after 21 hours of runtime!), but if I clean everything up, (Set ETCs to zero on completed tasks, remove assignees that aren't actually working on tasks, remove ~ from Task ID ~rmw, set allocations to reasonable numbers....we have some really awfully maintained projects, but they make good test subjects when performance improvements are announced!
The "Receiving Assignments" and the "Updating Assignments" steps are the slowest. "Updating WBS," which I expect would include your dependencies and dependency types, goes very fast (a couple of seconds), even in our poor project.
A project like this, we could not open before, so to get it opening in 12 minutes is perhaps a miracle. I will repeating the test in our 14.2 system, shortly, as there are some big advertisements being made regarding performance improvements. Looking forward to this.
I'm also a big proponent of CCPM (Critical Chain Project Management). IMO, CCPM offers a better solution for creating dependencies, scheduling projects and managing them. If you haven't looked at CCPM, yet, please do.