As for your paradox, I used to see it that way too but no more. I believe it is a natural process that will happen slowly. When there is demand both sides will adopt bitcoin.
As I see it, there are 4 scenarios:
1. Merchants make the first move and adopt it proactively so clients start using it more
2. Clients massively ask merchants to add Bitcoin option and those follow
3. Both happening simultaneously in roughly equal proportion
4. None of this happens and adoption stagnates