The comparison with the Shah of Iran is I think a bit strained. To an American it seems absurd and incomprehensible, but throughout the Gulf, even when there's criticism of a monarch, there's enormous respect for the monarchy, which is widely perceived as having inherent traditional legitimacy. That respect isn't universal - nothing in a populace ever is - but it's very widespread and is a real factor. A ruler who claims traditional power without actual blood right (the Shah) or rulers such as a Mubarak or a Saddam, who simply seized power, are seen as fundamentally different from a true traditional ruler. To us they're all just despots, but the distinction is meaningful in these places.

I've never noted any great enthusiasm for the idea of democracy in the Gulf, except among a few western-educated individuals, most of whom tend to keep it quiet. There's a very widespread perception that democracy would bring chaos and open the door for foreign domination. In much of the Gulf it's simply taken as a given that the American enthusiasm for promoting democracy is a vehicle for gaining power: the CIA would manipulate the elections (the ability to do so is presumed) and reduce them to US puppets.

It's easy to say this, and it sounds good:

We need to work to get straight with the governments AND the populace of both of these important nations sooner than later.
but when you get down to specifics, it always seems to presume influence that we haven't got, and to involve a level of interference in domestic affairs that's likely to be seen as unacceptable by both government and populace.

The cold war paradigm of dictators that are dependent on the US is not applicable here: these despots do not depend on us, and our influence over them is very limited. They are not client states and we cannot dictate policy changes or exert substantial influence over domestic policy. Neither governments nor populaces want us meddling in their domestic policies, no matter how high-minded our declared objectives are. These are peer-peer relationships, and if we treat them as patron-client relationships we will achieve nothing and antagonize everyone in the picture.

Meddling in the past hasn't given good results, but the answer to bad meddling isn't good meddling, the answer to bad meddling is less meddling. That won't change perceptions overnight, but neither will anything else. Attempts at good meddling will just reinforce the perception of self-interested interference: no matter what we say we're trying to accomplish, our actions will be interpreted as a self-interested attempt to gain control.