Due to buggy hardware or drivers, your monitor's correct resolutions may not always be detected. For example, the EDID data block queried from your monitor may be incorrect.
If the mode already exists, but just isn't associated for the particular output, you can add it like this:
$ xrandr --addmode S-video 800x600
If the mode doesn't yet exist, you'll need to create it first by specifying a modeline:
$ xrandr --newmode
You may create a modeline using the gtf or cvt utility. For example, if you want to add a mode with resolution 800x600, you can enter the following command: (The output is shown following.)
$ cvt 800 600 # 800x600 59.86 Hz
(CVT 0.48M3) hsync: 37.35 kHz; pclk:
38.25 MHz Modeline "800x600_60.00" 38.25 800 832 912 1024 600 603 607 624 -hsync +vsync
Then copy the information after the word "Modeline" into the xrandr command:
$ xrandr --newmode "800x600_60.00"
38.25 800 832 912 1024 600 603 607 624 -hsync +vsync
After the mode is entered, it needs to be added to the output using the --addmode command as explained above.
Source: https://wiki.ubuntu.com/X/Config/Resolution
Not 100% sure because you've got Intel graphics, but it sounds like the good old trouble with bad EDID. In a nutshell, your monitor sends bad info to your graphic card, it cannot read the maximal frequencies and errs on the side of caution, using the lowest possible settings only.
randr is (by design!) only meant for run-time changes. For any permanent configuration, you need to change your X server settings. For this, edit /etc/X11/xorg.conf (This is an important system file! Make a backup first!). You need to add HorizSync and VertRefresh lines. The result should look like this:
Section "Monitor"
Identifier "Configured Monitor"
HorizSync 30-35
VertRefresh 55-75
EndSection
Warning: Do not use the numbers I posted here! If you set a frequency in HorizSync which is too high, it might permanently damage your monitor. They fluctuate considerably between monitor models, I've seen them anywhere between 30 Hz and 75 Hz. You should look up the correct values in the monitor's user guide, or call the manufacturer's tech support and ask about vertical and horizontal frequency at your preferred resolution.
Maybe you'll need to add the mode line to the Xorg.conf manually (I forgot which section, I think Screen) but probably after the X restart you'll be able to set the resolution using the built-in graphical tool.
Even if this doesn't solve your problem, the xorg.conf is the place to save permanent changes to your screen configuration.
Edit, as an answer to your comments.
The HorizSync is the frequency, yes. On a nVidia card, setting the HorizSync and VertRefresh in the xorg.conf (then restarting X or just rebooting) makes all the usual resolutions available in the nVidia driver GUI. So choosing your preferred resolution there should be possible.
If this doesn't happen with the Intel drivers, you can manually add the resolution you want into your Xorg.conf. Still in the Monitor section, paste your modeline (which worked with xRandR). Then list the mode name as the Preferred mode option. Then, in the Screen section, Display subsection, add a Modes line, including the name of your mode.
The result should be something like this:
Section "Monitor"
Identifier "Configured Monitor"
HorizSync 30-80
VertRefresh 55-75
Modeline "1152x864_60.00" 81.75 1152 1216 1336 1520 864 867 871 897 -hsync +vsync
Option "PreferredMode" "1152x864_60.00"
EndSection
and below that, within the Screen section
SubSection "Display"
Depth 24
Modes "1152x864" "1024x768" "640x480"
EndSubSection
I am not sure if you need the Display subsection, but I have found it in an old config file of mine. If it doesn't work, comment it out again. Cannot test it on my current system because I cannot restart just now, and my current monitor configuration is different. So it may still need some tweaking. But in theory, adding the modeline into Xorg.conf is the permanent version of adding it dynamically to RandR.
If you need to tweak, a good information source would be the Xorg.conf manual. http://www.x.org/archive/X11R6.8.0/doc/xorg.conf.5.html
If all else fails, I think there is a X profile file where you can add xRandR commands. It is certainly not elegant, and possibly as slow as your init script solution. Besides, I don't remember much about this file and how to use it, so cannot help you there.
And if these things fail too, maybe the problem is something else. As it is probably still X related, you could look into your /var/log/xorg.0.log file. If there are lines starting with (WW) or (EE), google these lines and you'll almost certainly find a solution.
Best Answer
Well, I figured out what I was missing, it needed
--output eDP-1-1
. Still not quite sure why that isn't implied and what was operating on when I left it out, but it works now.