We present the discovery of planet-mass companions to two giant stars by the ongoing Penn State-Toruń Planet Search conducted with the 9.2 m Hobby-Eberly Telescope. The less massive of these stars, K5-giant BD+20 274, has a 4.2 MJ minimum mass planet orbiting the star at a 578 day period and a more distant, likely stellar-mass companion. The best currently available model of the planet orbiting the K0-giant HD 219415 points to a >~ Jupiter-mass companion in a 5.7 year, eccentric orbit around the star, making it the longest period planet yet detected by our survey. This planet has an amplitude of ~18 m s-1, comparable to the median radial velocity "jitter," typical of giant stars.