For a vivid example of this, see "Sailing Uma" on Youtube. It's a couple traveling by sailboat around the world. He has a Canadian passport, she has a Haitian passport. They don't talk about this much, but she frequently has much more onerous paperwork requirements in order to travel, even right up to being denied entry in some countries.
Earlier this year, they arrived in Europe and she got granted a ridiculous Schengen visa (see this video: https://www.youtube.com/watch?v=EgLBJXbkkQk). It has since been resolved, but it took the intervention of a high-powered lawyer who was either very expensive, or free only because they're "famous".
Honestly a pretty ridiculous system in my opinion.