Wow, there are a lot of threads popping up today on new ideas for Decentralized Exchanges. (I can't imagine why...) I started one myself 5 hours ago.
Allow me to throw some ideas on the fire, as this thread seems to have gotten further than the others.
1. Your concerns about how to port in real-world cash are unfounded. There already exists an industry of businesses that will take cash in many forms and give virtual credits, including bitcoins, for them... BitInstant, Dwolla, OKPay, coinbase, ArumXchange, and many others can upload cash into this exchange in one or more forms. Let them deal with this headache; there are many of them so there is no central point of failure there.
2. To really replace MtGox and have real-time graphs and trades like we all want to see, the core of this beast must always determine the other clients running within a short enough pingtime's distance. (So trades can happen in milliseconds, not multiple seconds.)
If a client logs on, looks around for other clients, & notes all of their pingtimes, the client can be a real-time, graph-displaying trading platform for everyone within a decent pingtime of you!
True, this means that someone in Kansas isn't likely to see the trades of someone in Perth... But that's the nature of decentralization. The going price of a bitcoin would therefore not be global, but regional... Although the regions are likely to be continents, not cities. You'd trade quickly with those closer to you (pingtime-wise) and if you can't find your trade there, I guess it would be a good idea to include an OTC board in the package too, or port in #bitcoin-otc somehow.
(Note: VPNs could be used for people that live far away from population centers to reduce pingtimes, too!)
3. No marketing will be needed. (!) If each client for this exchange gives the fees to the person running the client where the trade happened, then it is self-incentivized to spread much like how bitcoin miners get paid to mine. I've got some very specific ideas about how to make this part work, but for now all you need to know is that everyone with an internet connection would want to run this client because it would literally pay them to just run on their PCs. (And they wouldn't need expensive GPUs.) More details on this step later.
4. No miners needed. A lot of the data that runs across these clients need not be encrypted... You want the world to know what the current price for each currency is, for instance... It's just the ownership of things on it you must secure, so no processing of SHAs here, just good, secure ledger keeping.
Every client should be both a place for you to log in and make trades, and a place for other people to trade on. If run this way, it will use a bit of bandwidth (think: bittorrent) but not any advanced hashing that requires special equipment like GPUs.
Enjoy the ideas; I'll add some more later.