Mail was Steve Jobs' baby ever since NeXT, and it was built to be used (and useful) internally at NeXT/Apple. It's the best mail client I've ever used, in a sea of extremely poor mail clients.
I have had better luck with Sparrow, but even that has its bouts (its slows down all of a sudden and then comes back, which makes me suspect its doing some background compaction/garbage collection).
Even though I am no longer a huge fan of the Gmail web interface, it still works the fastest.
Perhaps it's related to either your specific hardware, gmail, or Mail's support for gmail?