Dunno what version of MySQL they're running, but perhaps you might take a look at
Omnis They're in Torrance, and seems pretty Linux-friendly. As an aside, I likewise am looking for a CA-based hosting outfit, and found Omnis via a link on the LQ Home page. (Note that I am not a current customer, but as I've been doing some research, they're looking OK) If you find anything interesting, please post back