I guess this problem is unavoidable short of using lots of different exchanges. Maybe there just needs to be more than one Coinbase.
The problem for exchanges especially (maybe to a lesser extent for "brokers" like Coinbase) is that they _need_ exclusive access to your bitcoins, to ensure there's no way for you to take them before they can give them to the other party in a trade. I don't see any way around this, short of exchanges trusting users to deliver bitcoins after the trade. Even with multisignature/escrow systems, there is the risk the user double-spends the coins at the same time they make a trade. (And if the exchange is able to take back the cash, or withhold it until the bitcoin transaction is confirmed, there's probably not a fair way in general to reverse the trade, is there?)
The decentralized order books in Ripple show this is solved. We don't need a central authority to match trades, no more than we need a central authority to prevent double-spends. When you post an offer to trade XRP for snapswapUSD on ripple, the XRP remains 100% in your control (until someone takes your offer and a trade is matched). Ripple shows how trade matching can be implemented as a decentralized cryptographic "contract".
Of course, this won't work with bitcoin as the native currency until somebody implements trade matching as a bitcoin contract (and exchanges like bitstamp issue bitstampUSD as colored bitcoins). And even then, there's still the fact that bitstampUSD is centrally issued and could all turn worthless the moment Bitstamp stopped redeeming it. And that has another solution (coins which track fiat-price in a decentralized prediction market).
When that kind of situation happens, people need to take the hint and stop using the service.