We present high-precision radial velocity (RV) observations of four solar-type (F7-G5) stars - HD 79498, HD 155358, HD 197037, and HD 220773 - taken as part of the McDonald Observatory Planet Search Program. For each of these stars, we see evidence of Keplerian motion caused by the presence of one or more gas giant planets in long-period orbits. We derive orbital parameters for each system, and note the properties (composition, activity, etc.) of the host stars. While we have previously announced the two-gas-giant HD 155358 system, we now report a shorter period for planet c. This new period is consistent with the planets being trapped in mutual 2:1 mean-motion resonance. We therefore perform an in-depth stability analysis, placing additional constraints on the orbital parameters of the planets. These results demonstrate the excellent long-term RV stability of the spectrometers on both the Harlan J. Smith 2.7 m telescope and the Hobby-Eberly telescope.