How does solution which electrodes are immersed in effect electrode potential?
The short answer is that we want a cathodic reaction so we can use the metals with a positive standard reduction potential (because 0 is for $\ce{H2} $ reduction).

In reality however to really find a suitable electrolyte cyclic voltammetry is typically used and electrolytes with suitable electrochemical windows for the cell reaction are chosen.


The electrochemical window is the voltages where the current is zero in the picture above. If the wrong electrolyte is chosen then a full redox reaction happens(with the electrolyte participating) rather than half reactions at each electrode negating the need for the external circuit and creating heat