A question of order with regards to the actions in this plot.

If I reveal respect of the old gods and opp reveals at the palace of Sorrows. If they choose me to go first would I be able to return the card of my choice to the top of my deck and then my opp returns his card to the top of his deck? Do they happen at the same time without an order?

Example:

If I have a frozen solid on his LMB and he made me first player. I choose frozen solid as my card and he chooses LMB. He says because he controls the plots and the effects of it he gets first choice and my frozen solid is discarded.

Any help is appreciated.

I don't think the order matters here. The rules say that attachments do not go moribund until the passive step of the action window, which is AFTER all "When revealed" effects resolve. So, you should still be able to choose Frozen Solid even if your opponent chose LMB since it is not yet moribund.

To answer the question though, the person who controls the effect always chooses first. So, the person who flips At the Palace of Sorrows, must choose first.

Doulos2k is right on both counts.

The person who controls the plot chooses first, but all chosen cards leave play at the same time.

Between that AND the fact doulos2k makes about attachments being discarded passively (after the entire plot effect resolves, NOT between each card leaving play), your opponent is doubly mistaken that your Frozen Solid is not an available choice for Palace, though he is correct that he chooses his LMB first, even though you are first player, because it is his plot.

Excellent. Thanks for the clarification everyone.