Hi HuskyHawk.
I understand your “misgivings” about Memory foam … while it does a very good job at minimizing motions transfer it will generally be the least breathable and most insulating of the foam comfort materials, so temperature can be an issue. There is a little more about the Memory foam in this article here In general terms Memory foam has very low resilience, has a more “in the mattress” feel to it, and changes its feel and response with pressure, temperature, humidity, and length of time it is subject to compression forces. It can feel firm in some conditions or circumstances and soft under different conditions. (As you’ve already seen in the pros and cons of memory foam article 
As far as the shoulder pains…first off, I’d make sure that you reevaluate your pillow to make sure that it is providing a decent alignment to keep your cervical/upper thoracic region in a relatively neutral arrangement. Improper pillow thickness is a common cause for shoulder issues, especially with a new mattress.
You may be looking in to the right direction with something plusher as you are both side sleepers and one of you has shoulder issues, which usually come from a mattress that is too firm and puts direct pressure on the shoulders, the shoulder blades, or on the back muscles and can also cause soreness or numbness and tingling in the arms or can often come from postural issues as well. If the mattress is too firm then if you sleep on your side your shoulders may not sink in enough to relieve pressure and your upper body can “twist” away from the pressure so your upper body is “twisted” more forward while the lower body is still on its side. This spinal twisting or torsion can twist the spine in the upper body and lead to soreness in the area of the twist. There is some much more detailed information on shoulder and arm issues in posts #2 and #3 here
Phoenix