It doesn't matter that Apple and Google aren't governments. Either app store approval could be done by a new government agency (after all, aren't doctors and lawyers regulated?), or (far more likely) the legislature could pass laws determining how Apple and Google have to run their own or face stiff penalties that actually have teeth.
So that, at the end of the day, if Apple or Google make a wrong decision and refuse to correct it, you can ultimately sue them in court and win.