Hi Kevin,
Congratulations on your upcoming marriage first of all! I would agree that it’s time for a new mattress 
I think that the first thing I would suggest is to eliminate the worst choices which hopefully will make it easier to focus on the better ones. The guidelines in this article will hopefully help.
I would also tend to avoid memory foam if you are not certain about how you feel about it. There are several reasons for this. First of all … with larger weights, memory foam may not be as durable as you would hope. If you do decide to go in this direction I would make sure that it was 5 lbs density at a minimum. Secondly … and I’m being diplomatic here … memory foam is not as “motion friendly” as other types of foam and many people rate it lower in terms of the other activities that can happen on a mattress because it can hinder movement. Finally, as you mentioned it can sleep hot for some people depending on many factors including the type of memory foam, the materials over the memory foam, and the thickness of the memory foam layers.
While the Garden Sleep System by Natural Form or SAT bed (self adjusting technology) may be one of the better air bladder mattresses … I would tend to avoid all of them for the reasons in this article. Bear in mind that an air bladder is only a support system and uses the same comfort layers as any other mattress so the air bladder should be compared to the qualities of other types of support rather than by how comfortable they may be because the upper layers are a big part of the comfort of a mattress.
I would also make sure that you are buying from an outlet who will tell you the type and quality of each layer of a mattress you are considering because that is the only way you can know the weak link of the mattress (which layer is likely to soften and degrade first) which will determine the life of the mattress. The heavier someone is the more important that more durable layers are used in every layer of a mattress but especially in the upper layers. This is also the reason I would avoid major brands and chain stores because they will generally use lower quality foams and not disclose the details of the foams and materials they use.
Different weights will perceive different firmness levels of the same foam or material very differently. A feeling of softness is partly dependent on how far someone one sinks into a mattress and heavier people will often feel a firmer foam as being just as soft as lighter people will feel with much softer materials. Because of your weight differential, what is called a “side to side split” construction may work well for you. This is offered by many local manufacturers at little to no extra cost and can “customize” each side of a mattress for different needs and preferences. I would also make sure that you test mattresses together as how a mattress feels can be greatly affected by a sleeping partner … particularly if there is a weight differential.
I believe that by far the best knowledge, quality, value, and service is at local factory direct manufacturers or at smaller sleep shops that carry local or smaller national brands. They will tend to offer mattresses that use higher quality and more durable materials at better prices.
I didn’t know which city you are closest to so I did a search centered around Macon and looked within about 100 miles for factory direct manufacturers or outlets which may offer better value. The list also includes the Atlanta region. They include …
http://griffinmattressco.com/ Local factory direct manufacturer in Griffin who makes more traditional polyfoam/innerspring mattresses in a lower budget range. He uses a minimum of 1.8 lb polyfoam with only thin layers of 1.2 lb polyfoam in the quilting which is higher quality than many major manufacturers use in mattresses with much higher prices.
http://www.tuckermattresscompany.net/ Local factory direct manufacturer in Tucker, Ga. A husband and wife team who make mattresses that also use higher quality materials including latex at lower prices. NOTE ADDED: Oct 23, 2015. Their website appears to be down but their contact information is on their facebook page here.
http://www.realpages.com/sites/mcdanielmattress/index.html Local factory direct manufacturer in Atlanta. They make a range of mattresses including memory foam, latex, and innersprings.
Find an Original Mattress Factory Store Regional factory direct manufacturer with an outlet in McDonough (and many all around Atlanta). They make a range of mattresses which includes memory foam as well as latex and traditional mattresses with good value.
http://verlo.com/ Regional factory direct manufacturer with an outlet in Peachtree city. They make a wide range of mattresses and are transparent about the quality of the materials they use inside them.
http://info.ikea-usa.com/ Store in Atlanta. Makes a range of mattresses including latex and innerspring. See post #3 here for some of the better choices here.
Some local retailers that are in the area and carry mattresses that may be worth considering (depending on their willingness and ability to provide you with the specifics of all the layers and components in their mattresses) and the brands they carry I would consider as a “possibility” include …
https://www.elementsofrest.com/ Atlanta, GA. They sell several component mattresses that use pocket coil modules with different firmnesses that can be used in different configurations and either memory foam or latex comfort layers can also be rearranged and zoned in different configurations as well. Rearranging the individual modules allows for a range of fine tuning options after a purchase.
http://www.mattressbliss.com/ Atlanta, GA. Atlanta Mattress. They carry a range of more premium mattresses including Pure Latex Bliss, Mattress Bliss, Posh & Lavish, and Magniflex along with VI Spring and Hypnos (which are ultra premium manufacturers).
http://naturalsleepandhome.com/ Retailer in Atlanta that carries Organicpedic (OMI) latex mattresses as well as Pure Talalay Bliss (Talalay latex), Naturepedic component mattresses, and Natura. All of these are high quality mattresses that use good quality materials but I would make sure you make some careful value comparisons with other latex mattresses because they are in more premium budget ranges. They also carry Anatomic Global memory foam mattresses and I would make sure you are able to find out the density of all the foam layers in these so you can make more meaningful comparisons with other mattresses if you are considering these.
The Green Pear Organic Mattresses | Alpharetta GA Retailer in Alpharetta that carries Savvy Rest latex mattress which is a high quality component mattress with a zip cover that allows you to choose the number of layers and the type and firmness of each layer but once again I would make sure you make some careful value comparisons because they are in a higher budget range than other similar component latex mattresses.
http://www.naturalmattressmatters.com/ They are a new store in Johns Creek, GA that carries Savvy Rest, Berkeley Ergonomics, Organicpedic (OMI), and Soaring Heart mattresses (see this topic for some feedback)
http://cantoni.com/ Retailer in Atlanta. Carries a private label version of Berkeley Ergonomics (see this topic) and Vi Spring (ultra premium mattresses).
Mattress USA - furniture, mattresses, and bedding in Norcross, Dawsonville and Gainesville GA Retailer in Norcross, Alpharetta, Kennesaw, Gainesville, GA. Carry Pure Talalay Bliss, Southerland, and Park Place mattresses. Be very careful here that you aren’t "steered’ towards major brand mattress which they may promote or to mattresses where they aren’t able to provide you the specifics about what is inside them or belittle requests for information that they may not be happy to provide.
http://mattresssandysprings.com/ Atlanta, GA. American Bedding, Golden
http://www.mattresspluskennesaw.com/index.html Kennesaw, GA. Jamison…
http://www.achooallergy.com/ Atlanta, GA. Royal-Pedic. Pure-Rest.
http://americasgreenstore.com/ Tucker, GA. Talked with her and they carry Suite Sleep latex mattresses and focus on people with MCS and chemical sensitivity issues.
ADSCHEAPER.COM - Best online advertising, affordable internet advertising! Roswell, Lilburn, GA. Jamison
http://www.sitnsleep.net/ Carrollton, GA. Jamison including latex, innersprings, and gel memory foam.
Furniture, Mattresses, Electronics, and Appliances in Cartersville, Kingston and Acworth GA | SAM FRANKLIN'S Home Furnishing Center Cartersville, GA. Symbol.
http://www.discountcityinc.com/index.php Cartersville, GA. Symbol.
There is also some feedback about some of the Atlanta options in post #1 here (thanks Diderot :)).
Your “best” first step may be to think of a mattress as different types of materials which are layered together in different ways to create different “feels” in terms of pressure relief, support, and preferences. These are generally materials that provide pressure relief in the top of a mattress and support in the lower layers. These are the two basic functions of a mattress. The most common materials used in the comfort layers of a mattress are here and in the support layers are here. I would use the local outlets to help you decide which materials you may prefer rather than focusing on brands. Once you know your materials preferences … then it becomes much easier to compare different mattresses by comparing the materials. I would completely avoid any outlet which is either unable or unwilling to tell you what materials are used in each layer of their mattresses. If a mattress uses either memory foam or latex it will say so and if there is a foam which doesn’t say one of these it will almost always be polyfoam in which case knowing the density of the polyfoam used (and most won’t know) becomes very important.
Once your local testing has helped you decide the materials and types of layering that you prefer in general, then the listed outlets are where I would focus my time and efforts (unless a local outlet happens to carry a mattress that uses high quality materials that you like and also has great value). I would do some preliminary work on the phone by describing your preferences, circumstances and “stats” to get a sense of the level of knowledge and helpfulness of each and the mattresses they recommend may be worth trying that use the materials that you prefer and in your budget range. After this you will have a good sense of the shorter list you may want to visit in person and test mattresses.
By focusing on materials rather than brand, you can get to the “overall feel” you prefer using higher quality “ingredients” … and you will be much better prepared to make more meaningful value comparisons between different mattresses.
Phoenix