My problem is that most graphical programs don't have a menu bar (File, Edit, View, etc.) when not on full screen (maximized) native built-in Ubuntu programs or third party stuff alike from VLC to calculators to native stuff like Nautilus
This problem (or default setting) existed since I first used Ubuntu 14.04 and now I am on Ubuntu 16.04.
If its a setting then how can I change it?
You can change it from settings. Go to System settings -> Appearance -> Behavior. There you will see an option "Show the menus for a window", and there are two choices. Either in the menu bar or in the window's title bar. Try both and use whichever you like.
PS: Please see the figure below.