Hi akaisha0.
Welcome to our Mattress Forum. 
As a hippy side sleeper myself, I can relate to a little of what you were describing. I can even relate to the cats that like to sleep by your back (although I also have one who enjoys sleeping down by my ankles and she gets mad when I move my legs at night).
Maybe, but maybe not! Phoenix has a super detailed post here about the various factors at play in the microclimate of a mattress that may prove useful to you in some way.
This is false. The issue boils down to durability (or density) over softness. It’s more than possible to purchase a soft but adequately dense and durable plush mattress. You can read more about that in our Durability Guidelines but the short version is that for your best bet, we would recommend that…
-For a polyurethane foam: If your mattress is one-sided then I would look for 2.0 lb per cubic foot density or higher. If the mattress is two-sided then I would use a minimum foam density of 1.8 lbs per cubic foot or higher.
-Memory foam (or gel memory foam): If your mattress is one-sided then I would make sure that any memory foam is at least 5 lb per cubic foot. If the mattress is two-sided then I would use a minimum density of 4 lbs per cubic foot.
If you were to choose instead a mattress with a 1.8 lb (polyfoam) or 4 lb (memory foam) density, you’re still going to get adequate support and a reasonably long life out of your mattress, but maybe not the full “lifespan” which, in most cases, maxes out at about 10 years, give or take.
I tend to be in the school of thought that if it’s not broken, don’t fix it but I can also see that this mattress is probably nearing the end of its durability lifespan and if/when that happens, you may start to experience sagging and pain on the mattress, so it’s good that you’re looking around.
I tried searching for your mattress, but I only found this one. Is this anything like your mattress?
You’re absolutely right. The break in period can be uncomfortable at times, but should never be excruciating. You made the right call in returning the mattress.
I’m unsure of the mattresses you mentioned without seeing their specifications in front of me.
I will say, Nest offers the Alexander Signature Hybrid in Plush.
And I browsed Mattress to Go and found this one that may be worth a look and this one amongst others on their site. These are full sized mattresses though, not “beds in boxes” so the shipping and delivery logistics are a bit more…exciting 
Keep in mind that no matter who you buy from, it is important to have a detailed conversation with whomever you choose to purchase from and provide them with your stats, body type, sleeping styles, general preferences and history, some general information about your current mattress, or what you have tested, and any other specific information or circumstances that could affect your choice of a mattress so they can help you choose which may be your best fit from their inventory.
I hope this helps!
NikkiTMU