Hi mikey,
First the easy part … post #2 here includes the better options around Charlotte.
It’s probably a good excuse to make some more extensive comments about your OMF experience as well because this is an issue that many people face no matter which manufacturer they buy from … and often with much more expensive mattress costing several times what you paid.
While they do have better quality and value mattresses compared to mainstream manufacturers, in the model you likely purchased they still use polyfoam that is more suitable for thinner layers and if you purchased their “top of the line” eurotop mattress … it will have a lot of polyfoam above the springs and this in combination with a queen or king size mattress will make “hills and valleys” unavoidable no matter who makes a mattress of this type. There’s more about this in post #2 here. Did an inspector come and measure the dips in your mattress … and how close were you to the 1.5"? Some manufacturers even have a warranty exclusion of 2" of sagging (with no weight on the mattress) or more before you can make a claim on the warranty.
Higher quality foam in a higher budget range which uses higher density HD or HR polyfoam or latex and much thinner layers of lower density polyfoam (which will soften) or fiber (which will compress) will have less issues with this. While this is unavoidable to some degree in most pillowtop or eurotop mattresses that use thick layers of low/mid density polyfoam in the comfort layers, especially in the larger sizes, it can be reduced with regular maintenance and flipping (for two sided mattresses) and the use of higher quality foams in thinner layers will also make a big difference.
Unfortunately at that time a lot of people were buying these types of mattresses (and still are) with very thick polyfoam comfort layers, pillowtops, and eurotops and either have or are finding out that none of them will avoid this issue. It’s only a matter of time and degree. Only very slowly are consumers starting to realize that this style of mattress is not likely to provide the long term performance or durability they are hoping for. How much this affects any individual person will depend on how close to their pressure relief and support needs they were when they first bought the mattress in combination with the degree of softening and any shifting or compression of materials in the mattress.
If someone buys a mattress that is more in the upper end or middle of the range of their comfort and support needs (in terms of firmness) … then with the inevitable softening they will be more likely to still be in their range for longer and they will be less affected by the shorter term compression and softening of the materials. If someone buys a mattress that is already “on the edge” of being too soft or not supportive enough (the “cushy” showroom pillowtop or eurotop feel that is the basis of so many buying decisions) … then any softening will put them on the wrong side of the line and they may experience the discomfort and pain that comes with this. In some cases with the initial more rapid softening of polyfoam and memory foam (the break in period) where they are already “on the edge” and chose a mattress that was too soft or thick for their needs … this can happen in a few weeks if the polyfoam layers are low/mid density and the comfort layers are too thick.
Because your mattress is two sided … then regular flipping and rotating can help with this (and eastern king size mattresses have the additional advantage that you can rotate them 1/4 turn as well as flipping them) but no matter what manufacturer you buy from … layers of polyfoam and or fibers in low to mid densities that are too thick will compress and soften and develop hills, valleys, and softer spots to some degree even with maintenance. It’s not the innerspring (which is not the weak link in the mattress) but the thickness and type of foam in the mattress. The only good news in this is that the same type of mattress with the same or similar types of materials (and probably only one sided) bought from a major manufacturer would have had the same issues for 50% (or more) greater price. There are many $3000 one sided pillowtop mattresses that use even lower quality materials than OMF and that will develop the same problem.
One other idea is that many manufacturers can rebuild your mattress using higher quality foams and thinner layers using the same innerspring and this may save you some money. I’m not sure if OMF does this but many local manufacturers do. The foams today are resilient enough that they will usually come back enough to be within the warranty exclusion even though they have softened to the point where the mattress has lost it’s comfort and support.
The moral of this story is to make sure you know the quality/density of all the materials and the layer breakdown of any mattress you buy so you can see any possible “weak link” in the mattress and more easily predict if this may happen.
On to the rest of your post …
Bedinabox are good people and I was impressed when I talked with them but they also use low density memory foam (3 lb memory foam) in their mattresses which can soften faster than higher density memory foam. The good news is that they are often more flexible with the “gray areas” of their warranty coverage. The Pacbed also uses only 3" of memory foam and it also uses a very high quality polyfoam support layer which means that softening may be a little less of an issue than if the memory foam was thicker. While I would personally avoid the use of 3 lb memory foam in any budget range … at least it has better value than many other very low density memory foam mattresses in a similar price range that are sold all over the internet. As an example … for not much more … you could purchase rockymountainmattress.com/cottonwood-p-33.html something very similar with higher quality (but still not as durable as 5 lb memory foam) 4 lb memory foam.
There’s lots of information in the “mattresses” section about different materials mattress construction, and layering guidelines. Bearing in mind that the issues in your mattress were not about the inerspring … it sounds like you are headed in the direction of specialty foams which means either some kind of memory foam or some kind or latex. Both have good motion separation in a good construction although memory foam would have the slight advantage here. Latex is more motion friendly and more resilient and supportive. They are about equal in pressure relief and latex is cooler sleeping than memory foam and more durable than even high quality memory foam. It’s also more expensive. I would definitely make a point of doing some local testing of both to see how you feel about both in various constructions.
Link is at the beginning of the post.
That depends on how you feel about the difference between memory foam and latex. This is usually best decided either with the help of a local manufacturer who can help you with testing their mattresses (most accurate) or with the help of an online manufacturer who knows every detail and component of the mattresses you are considering and how each part interacts with the others and with different types of people and sleeping styles. Even small differences in components like different types of ticking and quilting can affect these types of choices and since they know all the options and fine details of their mattresses … they are usually much more accurate with “blind” advice based on what their “average” customers prefer without a specific reference point of mattresses with known materials you have tested.
There are some general weight/height/body shape guidelines here though and some sleeping position guidelines here but it’s always easier and more accurate and effective to work with the person selling a specific mattress and who has years of experience with the art and science of fitting a mattress to a person than to get too involved in “theory at a distance”. The more the person helping you knows … the less you have to know and the overviews will give you enough information to be able to ask good questions and make sure that the answers made sense. With some basic knowledge and the help of an “expert” that is committed to helping you make the best choice of the mattresses they sell … your body will tell you which mattress works best for PPP (pressure relief, posture and alignment, and your preferences … such as motion separation).
The advantage of higher budgets is usually greater amounts of higher performing materials but even more important greater durability. More durable materials are more expensive. Even very low budget materials can perform well for the short term … they just don’t keep their original properties or last as long. Budget is always a personal preference but in the $700 - $1000 range (queen mattress only) or so you can find good quality and durable mattresses and as you move towards the $2000 range you can find more and higher quality materials and great mattresses (that would cost significantly more if you were shopping major brands or in mass market outlets) and as you move into the $3000 range you can find absolutely amazing with more higher quality materials or special features or construction methods. There is little reason to go beyond this (or in many cases the level below) unless you are looking at a “work of art” that has value to you for other reasons than performance and durability.
Given the “extreme” urgency 
… the most effective approach is to first scan the basic information the tutorial post and the overviews so you can ask better questions and the answers will make more sense. Next decide on 2 or 3 outlets before you think too much about any specific mattresses. Always phone first and talk with the outlets on the list and discuss your needs and preferences and ask lots of questions about what they make or sell that they think would be worthwhile for you to test. Never visit an outlet before you have talked with them to “scope them out”. Once you’ve recognized the better outlets that you best connect with and who are open about the materials in their mattresses and you’ve narrowed it down to 2 or 3 places that you feel comfortable with their level of knowledge and service … then visit these ones and choose the best at each outlet. This will give you final choices between “good and good” and while it can be difficult to make the final choices … at least all your choices will be better than they would have been if you had been shopping by “following the advertising” or looking for “name brands” that are sold by people who know more about marketing stories than they know about mattresses.
You have some very good choices available … and feel free to post any questions you may have along the way if you come across anything that doesn’t make sense to you.
Phoenix