We have a few customers using Magento on a shared hosting environment. The page load times are in the 10--12 second range... very slow by anyone's standards. I've tried optimizing MySQL and Magento on my own but I think it's time I find someone who really understands how to do this... is there anyone out there who can help? I'm not opposed to paying you for your time.
optimization on shared is not so easy, because you have not much options.
only debug your theme and install full page cache
Start by checking your db usage - if you have access to the db memory stats.
Actually on a shared server your options are a bit limited, although there are some good Magento-optimised shared server hosts.
I would actually start by sticking your sites on GTMetrix.com - you can save a few sites on the free plan and it will show you where you can optimise your site for speed. If you get it showing a rated A and it's still slow then you might want to look at a different server.
I pretty much have access to everything on the server, I'm just fairly new to Magento. Like I said earlier, the pages load fast after the db query... so it's the db query that's the bottleneck. I'm sure it's a matter of optimizing MySQL for Magento. I would like to learn how to do this (or even pay someone to do it for me) so I could host other Magento websites.
For this particular Magento installation, so far I have chosen the options to combine css and js files, and use compilation. It has helped some but there's lots of room for improvement.