I would choose a very small niche. The chicken-and-egg problem disappears almost complete if you choose the niche small enough. This can be a movie category or a region, maybe the movie category is better in your case.
Because, if the niche is small enough, you will always be able to handle the short coming of the other (supply/demand) side in a realistic way, be it by cold calling or adwords or whatever.
I would stick with this niche for a while. You will have some first successful transactions, some success stories, some data you can use for statistics and pr, generate modest earnings, build up some ranking positions on google, etc... and you start understanding the numbers of your business, the conversion rate, etc..
And you will provide traction for your current users. Promoters that have signed up for the newsletter will regular receive some opportunities, and this is what counts to make your useres happy in a marketplace.
When your first niche is doing well, you can risk the next step, expand two other segements (categories). And repeat.
From my point of view, the critical thing is that you will loose a lot of ressources everytime you start acquiring new customers/segments. There will always be a mismatch of the demand-side and the supply-side. To be successfull, you needed to cover one segment by segment, otherwise you may run out of time and money before you get significant traction.