Sinnoh Stones only from certain PVP leagues?

You can get them from any league. Same goes for challenging one of the team leaders. To my knowledge, the odds of getting one are the same in all three leagues as well.

Totally random - I've had them from all three leagues.

I've been battling in each league once per day while eligible for rewards. Yesterday my partner got one in the great league, I got one in the ultra league, and neither of us got one in the master league.