Hi Randy20000.
Welcome to our Mattress Forum! 
It seems that you are facing the classic dilemma of a couple with very different needs and preferences that need to be designed into the same mattress or “sleeping system”.
One of the most common approaches used to solve these type of challenge and take into consideration the unique needs and preferences or each sleeping partner is a “side to side split” mattress construction. In this approach each side of a mattress is layered differently to take different needs and preferences into account. In effect you would have two different mattresses on each side combined into one cover (or in some cases a different topper on each side of the same mattress) and each side would feel and perform differently. The mattress can be built so that the total thickness of the mattress is the same for each side, which means that there would be no difference in elevation, and with a suitable tight fitted quilted cover the “split” transition area between sides is usually unnoticeable for most people. You can read more about this in post #2 here
A split mattress (most commonly available in a split king which is two twin XL mattresses but can also be made in a split queen by some manufacturers) can be a good way to accommodate very different needs and preferences although of course the “gap” in the middle can be a little bit of an issue for those who prefer to sleep in the same mattress and use the “split” in the middle of the mattress, but the possible discomfort will be not so much because of the “split” itself but because of the difference in the firmness levels of the two sides. The bigger the difference between the sides… the more noticeable the transition area in the middle and… of course this also depends on where on the mattress each person sleeps.
There is more about split king mattresses post #8 here and in this topic.
Which of level of comfort/plushness and support/firmness would work best for each partner would depend on the needs and preferences of each person in the couple. Careful testing can help you determine the level of comfort/support you each need and if you are considering an online choice where you can’t test the construction in person this is where the help and guidance of a knowledgeable and experienced manufacturer or salesperson who knows every detail of the mattresses they make and sell, how they interact with different people and couples, and that has your best interests in mind can be invaluable.
Out of the whole range of opinions that many different people would have about split layering, talking to manufacturers such as SleepEZ (which is a member of our site) and others who actually make mattresses with split layering will probably be the best source of information. Their focus is much more on informing people than it is “selling” to people so they would have a large “database” of feedback all along the spectrum of opinions and individual “reactions” to split layering and what they tell you can be trusted and would give you a much wider range of responses and possibilities that may affect you.
[quote] I know that there are memory foam mattresses that one can buy with two different firmness levels, but are there more conventional (coil springs, pillow top) that can also have differing firmnesses? (I’m not huge on memory foam beds, but not opposed to them per-se).
Any thoughts you have or places that you could point me in the right direction would be much appreciated.[/quote]
Memory Foam Comfort (member of our site) has a memory foam component-style system that you may wish to enquire about.
Another option would be a core split construction and a solid comfort layer on top which will moderate the feeling of the different firmness levels of each side below it and take the “edge” off the “split” in the middle. Arizona Premium Mattresses has a core split which contains a 6" split support core of 100% natural Talalay latex in your choice of 3 different firmness levels and a 3" solid comfort layer with two different firmness options. It has a bamboo cover quilted with natural Joma wool. All of these components are very high quality materials and there are no lower quality materials or weak links in the mattress.
SleepEZ split mattress is this one. This mattress has split firmness layers in each of the three 3" layers of either 100% natural Dunlop or 100% natural Talalay in your choice of 4 firmness levels for each layer and has an organic cotton cover quilted with organic wool. This mattress also uses very high quality materials and there are no lower quality materials or weak links in this mattress.
Another possible option would be a system using pocketed springs where you can put different springs on each side with different foams on each side as well such as ZenSpring from Savvy Rest.
While your own careful testing or personal experience is the most reliable way to know whether any mattress is a good “match” for you in terms of comfort and PPP(Posture and alignment, Pressure relief and your own Personal preferences) … when you can’t test a mattress in person or you have “out of the norm” situation then the most reliable source of guidance is always a more detailed phone conversation with a knowledgeable and experienced retailer or manufacturer that has your best interests at heart and who can help “talk you through” the specifics of their mattresses and the properties and “feel” of the materials they are using as they relate to your situation and the options they have available that may be the best “match” for you based on the information you provide them, any local testing you have done or mattresses you have slept on and liked or other mattresses you are considering that they are familiar with, and the “averages” of other customers that are similar to you. They will know more about “matching” their specific mattress designs and firmness levels to different body types, sleeping positions, and preferences (or to other mattresses that they are familiar with) than anyone else.
Aside from this I would make sure to revisit the mattress shopping tutorial here(there is a condensed version of it at the end of that post) which includes all the basic information, steps, and guidelines that can help you make the best possible choice … and perhaps more importantly know how and why to avoid the worst ones.
When assessing any product and before making any purchase also be sure that you find out information listed here so you can compare the quality of the materials and components to the durability guidelines here to make sure there are no lower quality materials or weak links in a mattress that would be a cause for concern relative to the durability and useful life of a mattress and all the other parts of your personal value equation that are most important to you (including the price of course and the options you have available after a purchase if your choice doesn’t turn out as well as you hoped for).
I’ll be interested to learn about your progress and find out what you decide. I’ll be happy to assist you with any other questions you might have.
Phoenix