Multithreading *is* the best way to keep the UI alive -- if you were doing work on the main thread the UI wouldn't react at all.
But WPF is a slow and complex framework that really requires a powerful video card and a multicore CPU to run well, especially if you're doing simultaneous work in the background. WPF rendering is itself multithreaded, so what you're seeing is thread starvation as the system just isn't fast enough to service all those jobs at once.
What you could try is lowering the priority of your worker threads, using the Thread.Priority property. If that doesn't help you'll have to keep inserting Sleep calls at strategic locations, just as you do now.
Things would be better if we could deliberately wait for a WPF UI update to complete, as discussed in this thread:
http://social.msdn.microsoft.com/Forums/en-US/wpf/thread/693fbedb-efa6-413e-ab66-530c6961d3fbUnfortunately that still isn't possible, so we're left with workarounds like lowered priority or sleeping...