I have never experienced a loading slowdown, but my blog is small.
If you search I'm sure you'll find more complete analyses, but off the top of my head.
Reduce the number of db calls. eg. if your theme is relatively stable, you can hack the files, replacing calls like get_bloginfo('name') with the actual name.
Even if you have a lots of posts, they are only called for certain pages. Other things are called every page load i.e. options
WordPress has gotten better at self-cleaning old cached feed content, but if you have tried a lot of plugins/themes they may have added options that are left behind when you delete the plugin/theme (IMHO plugin authors should really be putting that into the plugin code, but ....)
I have heard from some of my plugin users that their load time improved a lot after they removed orphaned options. But the fact that older versions didn't remove cached feeds was the main culprit, some users had literally hundreds of obsolete rows bloating the options table.
And has been mentioned, optimizing the database from time to time isn't a bad idea either.