Would a PC with the Sentinel feat have an opportunity attack against a Bulette which is trying to burrow? If so, would it able to burrow with 0 movement speed (In place in the same square)? Does size make any difference in stopping such a large creature?
I would say yes, given the following in PHB 195:
The [opportunity] attack interrupts the provoking creature's movement, occurring right before the creature leaves your reach.
So, if you can see it trying to burrow and it's within your reach, you hit as it tries to leave, and then it can't move any further.
And no, size makes no difference to Sentinel (features/spells/feats that take size into account mention it explicitly. I.e., Ensnaring Strike agrees with your intuition—it's a spell that attempts to hinder a creature, and anything Large or larger has advantage on the saving throw. As you can see, however, Sentinel doesn't have a similar caveat.)
No, you do not get an attack of opportunity
Page 195 of the Player's Handbook says the following (emphasis mine):
You can make an opportunity attack when a hostile creature that you can see moves out of your reach.
Having the sentinel feat doesn't change this requirement in any way.