Thank you so much to all the people who contributed to this rich and awesome thread!
There are some very interesting stories and perspectives on the chicken & egg problem and it's very educating and motivating for those who think about launching, as well as for those who have already begun.
As for me, I run
FitMyTime.com - a marketplace for online live one-on-one fitness and yoga classes. On the supply side there are instructors who are interested to expand their customers list by training clients remotely. On the demand side - people who need a personal training and prefer to work out from the comfort of their home, in their language (there are language and activity type filters). Those can be busy moms, people with tight work schedule, people with gym anxiety/discomfort, people who are in a recovery process and so on.
As for the chicken & egg problem - I started with the supply side. I began with reaching out to trainers I knew personally. We also did a pilot to understand how does it feel to workout with a trainer remotely. Next, the trainers I recruited brought some of the friends (also trainers/yoga instructors). This phase wasn't easy and required a lot of effort, and of course I manually listed the trainers. After I had around 15-20 trainers I started publishing on trainers job boards. That phase was easier and the trainers created the listings without my help. Today there are more than 100 instructors, and I'm not looking for increase that number dramatically soon. The next step for me is to increase demand in order to reach liquidity.