My wife and I went to Macy's, which has an extensive mattress selection and assorted discounts if you're clever with the coupons.

They have a house brand, which is pretty good, as well as carrying many other brands. You really have to plop yourself down and spend a few minutes relaxing on each mattress to get a feel for it. We ended up with a king-size fairly firm mattress, of the sort that cannot be flipped. Four years on, we still love it.