Sprung, with a memory foam pillow top. Best of both worlds.

I agree with EJ. I had memory foam for years and I just got a spring, and I kinda miss the foam.
I'd lean toward foam if you just want one thing.
If you're someone who gets hot and sweats at night then maybe spring, but I am always cold and like the little extra warmth that foam provides.

This is the one I bought a few months ago. It's incredibly comfortable.

Futon.

Whatever you do, make sure you can flip it. I have a mattress that has a pillowtop on only one side, and I'm not loving that aspect.

Actually, I'm not a fan of pillowtop in general. I feel somewhat suffocated. And I haven't had foam before, but I tend to being warm and suspect I'd hate it.

Consider this a vote for spring mattress.

Oh, I can't do a futon anymore - at least not one without a mattress underneath. My problem is that a lot of beds feel really hard to me - unsupportive, boardlike, too firm. I really want something that feels both soft and supportive.

I have a truly shitty old mattress now that for ages I just couldn't afford to replace. I think I can buy one now, but I'm baffled by the array of materials choices and price points. In the morning, I wake up actually hurting in the back and shoulders because my bed is so crappy. I don't sleep deeply. Whenever I stay at a hotel or someone else's house I invariably sleep like the dead and wake up feeling fantastic - which tells me their mattresses are just way better than mine. I always check the label on hotel mattresses, but they tend to be either obscure hotel brands, or impossibly high-end for my budget. And I've never slept a night on memory foam, though it does sound like I'd like it.

I was interested to read a website where memory-foam sleepers rated their mattress comfort a lot higher than innerspring people. That almost had me convinced until I realized that the memory-foam contingent is probably the most likely set of people to splurge on that sort of mattress, meaning they're the most likely to be unhappy with innerspring, and thus the happiest with their choice.

We were going to get a memory foam but my wife tried it and did not like the feel. Others swear by them. Apparently far less tossing and turning over the course of the night.

(Idly wondering if sex would be any different on memory foam. . .)

In case you hadn't seen this recent askme about mattresses: here ya go.

Memory foam.

You know, I've wondered about this myself. I'm about due for a new mattress myself, and I've looked into the foam thing. I almost pulled the trigger on a Costco one when they had a sale recently. I had read up on them, and they are rated very well. Thing is, I'm a side to belly sleeper, and I wonder how comfortable the foam would be for me. Then there's the whole sleep partner thing too. I'm betting a sure bet would be the cat will love it.

So, to add to your confusion, I'm flummoxed as well.

Memory foam, but keep in mind it's warm, and a little firmer than you might think. It really is supportive and comfortable; like cheesecake in more ways than one. Also, tossing and turning doesn't disturb your partner.

A compromise for the "Foam? Or springs?" argument is to get a good quality sprung mattress and a separate memory foam mattress topper.

I have to say, I absolutely love my pillow-top mattress. Before I had it, I had a Sealy orthopedic mattress and I put a duvet (comforter) between the mattress and the sheet to act as a topper. But I am like the Princess and the Pea when it comes to beds, and I have to have the perfect mix of firmness and comfort to get a good night's sleep.

We're a little over a year into a Keetsa memory foam mattress. On balance, I like it but don't love it. Curiously, it feels a bit hard to me sometimes; i wish it had a bit more spring-back to it. It also sleeps very warm - I like the room cool, with cool sheets, etc. I'm often uncomfortable under a down comforter that was not too hot on our previous rig.

FWIW, Moving a memory foam mattress is tough - they're heavy and limp. You know how kids get heavier when they fall asleep in your arms? Like that. They ship vacuum-packed so they're a bit more manageable, size wise - although just as heavy.

(Danf: You don't get a "bounce" to work with.)

I love the Stearns & Foster innerspring set I bought about 10 years ago. It's cushy with good support and still in good shape.

I've never slept on, or even tried, a memory foam bed. The sleeping hot part would really bother me.

Memory foam is very heavy, something to consider if you ever move. I think a queen tops in around 150lbs, and has the consistency of a burrito when lifted.

Oh, missed triodes above.
Moving buddy and I did a down one flight and up the other with a queen size memfoam as an experience to remember. I am surprised the siding did not tear off.

One thing that I am considering is to buy an innerspring mattress and a separate memory foam topper. That removes the one-sided topper problem and also means that you can swap out either component without the other. In my experience, coil-spring mattresses rarely last more than 7-8 years before garnering the sort of dips that make them uncomfortable. So you may as well buy a comfortable mattress in terms of firmness and then add comfort with a topper. Ikea do some reasonably-priced foam mattress toppers of various qualities.