As this is so unbelievably easy, and made such a huge difference, I thought I'd write it down in case it vanishes from elsewhere and someone else is suffering the problem.
Every time I tried to download in firefox it would take an ice age to even start the download, completely locking it up and making it unusable, it just completely froze.
Simply, the problem is that if you haven't asked firefox to remove links to old downloads or have set it to manual it freezes the whole thing while it digs that long list out for you. To fix it, go to Tools->Options. Switch to Privacy then select the Download History tab. Now change the option in the "Remove files from download manager" dropdown to either "when the download completes" or "when firefox exits". Hit OK and bingo, problem solved.