Hi Mitzi.
Welcome to our Mattress Forum. 
Thank you for sharing the details surrounding your experience with your new mattress. Sorry to hear you find it over-firm but I am glad that you reached out. It is easier to fix a firmer good quality mattress than a softer or sagging mattress.
Yes…. a good quality topper can certainly be an effective way to add some additional softness. Toppers are designed to add comfort to a mattress that does not sag but is too firm and needs some pressure relief qualities. When you use a topper over a mattress the topper will compress and in combination with the layers below it will take on the shape of your body profile. Softer toppers will compress more than firmer toppers. This “cradle” formed by the upper layers re-distributes weight away from the pressure points of the body.
Sometimes choosing a topper can be as difficult as choosing a mattress as it takes a bit of trial and error to dial in and find the exact combo of support/comfort best for your needs. The good news is that if you do end up making a suitable topper choice and the mattress/topper combination turns out to be a good “match” for you in terms of PPP then it also has the advantage of being able to replace just the topper without replacing the entire mattress if it softens or breaks down before the upper foam layers in the mattress (the upper layers or a sleeping system tend to soften or break down before the deeper layers) or if your needs or preferences change over time and a topper can also help extend the useful life of the mattress underneath it as well.
I would be cautious going wool only topper direction as it tends to compress over time and to form a permanent cradle of compressed fiber.
You are correct about s down/feather topper or featherbed or a fiberbed is more “fluffy” than resilient and while it can provide some degree of localized pressure relief under pressure points … it is much less resilient than a foam topper and won’t redistribute your body weight as effectively or provide the same degree of pressure relief as a foam topper. It will also pack down and compress more, requires more maintenance and regular “fluffing”, and with your weight, it also won’t be as durable as a good quality foam topper. There is a little more information about featherbeds and “down alternative” fiberbeds in post #10 here and in post #6 here and in this topic about featherbeds.
A latex topper seems to be the best option for you as can be a comfortable choice to provide a bit of extra plushness, but also something that provides a bit of support. Latex has an unusual combination of surface softness and deeper firmness/support that comes from its elasticity, its point elasticity (ability to conform to the shape of a body), and its compression modulus (the ability to get firmer faster with deeper compression than other types of foam). This means that it can enhance the pressure-relieving layers above it because of its surface softness and point elasticity but it is also very supportive and can “stop” the heavier parts of the body from sinking in too deeply. You’ll ultimately end up with firm on firm and you won’t get the pressure relief you are looking for. You mentioned that both you and your partner are on the low end of the BMI range, and side sleepers.
As far as instructions for selecting a topper, there is more information about choosing a topper in post #2 here and the topper guidelines it links to, which along with a conversation with a reliable and knowledgeable supplier (that can provide you with good information about how their toppers compare to each other or to other toppers they are familiar with that are available on the market), can help
In general, a good starting point for a good comfort layer for a side sleeper is 3" and then depending on weight, body shape, preferences, and the firmness of the support layers, to go up or down from there. Most side sleepers will fall in the range of from 2" - 4".
Side sleepers with inadequate comfort layer(s) will experience all the things you listed and more.
And as you are both low weight sleepers, you may need a softer layer that allows you to sink down enough to receive the comfort and support you need and desire.
I’d start by keeping in mind that toppers, like mattresses, are a comfort choice, so your preferences for components, fabrications, thickness, etc. will all factor into your selection.
I would review the information in post #2 here and the topper guidelines it links to (including detailed posts about wool, featherbeds, and latex toppers)that can help you use your actual sleeping experience as a reference point and guideline for choosing the type, thickness, and firmness for a topper that will have the best chance of success.
That all said, as you have a preference for natural components and need something that will soften your current sleeping experience, I would suggest looking at latex toppers.
We also have topper guidelines you may wish to review - but the short version is:
If the mattress needs just a “touch to a little” extra softness or a softer “surface feel” … then a 1" topper is usually enough.
If you need a little to a fair bit of extra softness and pressure relief … then a 2" topper would be in the average range. Given that you are both lighter this may prove to be a good option for you.
If you need a fair bit to a lot of extra softness then a 3" topper would probably be a good start for higher BMI sleepers or those experiencing numbness, tingling, or arms falling asleep.
Generally Heavier weights generally do better with firmer and thicker toppers. Lighter weights generally do best with softer and thinner toppers.
Once you get a chance to peruse the information and links mentioned above I’d make sure to check out our Trusted Members here Most have good quality toppers and I have no doubt that they will not hesitate to help you find the best combo and thickness/softness they have available that works for you. As you’ve already gathered, It usually takes a bit of trial and error and a bit of time spent on the mattress to ensure that you dialed in the best mattress/topper combo for you. I’d make sure that whatever you chose has a good exchange policy as you won’t be able to take your new mattress with you to a shop to test the mattress/topper combination as they do not work in isolation.
I look forward to any progress updates or questions you may have moving forward.
Phoenix