The Ace
Scottish Roman.
I think "my liege" was a form of address to a liege-lord under the feudal system. This did not have to be the King.
Prior to "your majesty" I believe the English King was addressed as "your grace" (as George Martin uses in his Song of Ice and Fire), an address still used for bishops.
The first Scottish monarch to be, 'Your Majesty,' was James VI, after he went South.
Technically, the correct form of address for the King (or Queen) of Scots is, 'Your Grace,' even now, but they've grown used to being majestic.
'My Leige,' - is exactly that, the address of one noble to a superior, which is why a duke or earl would use it to his king.
Nobles could also address one another as 'My Lord/Lady,' (of)[title].
While correct matters of etiquette are often highly complex, a commoner would get away with, 'My Lord,' or, 'Your Honour,' because they wouldn't be expected to know any better (although - depending on your character - they may receive swift instruction), but a Noble would be instructed in the forms from an early age, and they would be second nature.