Maybe it's just an impression, but in Claws setting a folder to show only unread messages and collapse threads seems to help.
I have my mail organized in various folders and the only one that gives me some problem is a mailing list archive with ~30000 messages, the rest are fine, but it may also be because the server is on my lan and it's cyrus. I don't have many messages on gmail, so it also works fine.
Note that the downloading of all headers should happen only once, then it'll only download the differences.