Strictly talking about desktop navigation:
It is really going to depend on the content displayed but under ~970 px width and/or ~400 height do not use a sticky menu, the menu is going to eat the content. Be responsive in that matter.
Do not be afraid to go big, Facebook menu is about 90 px high and feels really natural. Did you realized that Gmail is in fact using a super Huge sticky menu of 160 px high?
Under 1045 px it is reduced to ~110 px
The question is: when and how the menu is going to be helpful to interact with the content? The size of it is going to be a consequence of that reflection.
Do not be scared to see big it is not an issue.