Maybe you should separate the issues of (1) building a two-sided marketplace from (2) providing a great user experience. I'd put all my energy into (1) until you can convince yourself and everyone who matters why you're going to nail it. The most awesome user experience doesn't matter if there's no one in your marketplace.
I'd definitely read the link @Ben posted and gobble up as much info as you can on building two-sided marketplaces (there are several threads on FD and a ton of great Googleable material).
imho, it comes down to Single User Utility. We all know that after you build your network, you'll be phenomenally successful but on day one how/why does someone get material value from the service? If they don't then you've got to figure out how they do. This is not an exercise left to the reader... if you can't figure it out, then you really don't have a business.
Usually, but not always, the answer is building out one side of the network first and it's typically the supply side as those are the folks that want to be found and getting their data tends to be much easier.