Try replacing the HDMI cable that came with your Steam Link with another (preferably thicker) one to eliminate the cable from causing problems.

*These instructions require a USB thumb drive*

Your Steam Link boots at 480p (Steam Link logo), then switches to 1080p by default.
You can change the boot resolution to any of the following:

1080p
1080i
720p
480p
MV_PE_VOUT_FORMAT_720_480_I_5994
MV_PE_VOUT_FORMAT_720_480_I_60
MV_PE_VOUT_FORMAT_720_480_P_5994
MV_PE_VOUT_FORMAT_720_480_P_60
MV_PE_VOUT_FORMAT_720_576_I_50
MV_PE_VOUT_FORMAT_720_576_P_50
MV_PE_VOUT_FORMAT_1280_720_P_25
MV_PE_VOUT_FORMAT_1280_720_P_2997
MV_PE_VOUT_FORMAT_1280_720_P_50
MV_PE_VOUT_FORMAT_1280_720_P_5994
MV_PE_VOUT_FORMAT_1280_720_P_60
MV_PE_VOUT_FORMAT_1920_1080_I_50
MV_PE_VOUT_FORMAT_1920_1080_I_5994
MV_PE_VOUT_FORMAT_1920_1080_I_60
MV_PE_VOUT_FORMAT_1920_1080_P_24
MV_PE_VOUT_FORMAT_1920_1080_P_25
MV_PE_VOUT_FORMAT_1920_1080_P_2997
MV_PE_VOUT_FORMAT_1920_1080_P_50
MV_PE_VOUT_FORMAT_1920_1080_P_5994
MV_PE_VOUT_FORMAT_1920_1080_P_60

Here's how you do it:

1. On a USB thumb drive, create a folder named steamlink
2. Inside your steamlink folder, create a folder named config
3. Inside your config folder, create a folder named system
4. Open a new document in Notepad (or another plaintext application), enter the desired boot mode (for example, 720p or 1080i), and save it as display_resolution in your system folder
5. Remove the USB thumb drive from your computer and put it into the Steam Link
6. Power cycle the Steam Link. You should now be seeing a new resolution.