The only way to improve it is cache it for maybe x minutes, and then update cache. Maybe you should provide the reason why it can't be cached for say maybe 5 minutes. If its a problem where they are reloading, the homepage to see results then you could do incremental updates of each section using comet technique.
This is probably a more practical method.
If it has to be updated on every page load I don't think there's anything you can do...I may be wrong I'm sure someone on HN will have some performance tricks. You can generate your headers and footers and store them in a file instead of touching a database every time. If you're killing your database server you're probably returning too many records or your queries suck. I wouldn't know without seeing them.