I wish I had known about this one sooner!
Out of all the things I've tried to speed up my Drupal site, nothing has had anywhere near the dramatic improvement the CDN integration module has given me.
Before activating this module, my site would take 50 seconds or more to load for an anonymous user, and could take longer than 120 seconds when I was logged in as an admin, depending on what I was trying to do. I would also get a lot of 500 Internal Server Errors and WSOD failures while logged in.
Now, as an anonymous user, the site loads in less than 8 seconds, and 12 - 50 seconds as admin, depending on what I'm working on. So far, I've hardly had any Internal Server Error messages or WSODs, I'm only using this in Basic Mode and according to YSlow there's still some improvements that should be done. I'm happy with the way Basic Mode is working for now, I applied this directly to a live site, but I'll play around with the Advanced mode on a test site later.
I had to apply the included patch to get it to work (see http://drupal.org/node/568926 for more details), but I'm glad I went through with it (my first attempt to apply a Drupal core patch!).
Now to build a new site using this module from the very start!