I just don't fit in a single bed - I'm 6'1 or thereabouts, so my feet stick out the end and get cold. Here at Uni anyway.
Got a double at home, and will do next year in my house for uni. Much better - I can stretch out when I'm alone, and I don't crush my girlfriend if I'm not (we can sleep in a single, but it's a bit cramped and is a pain sometimes, particularly with the arms).
Therefore a double bed at least.
Although the comfiest bed I've ever slept in was the smaller-than-single, wire-and-metal framed, 2" thick foam mattress bed in army barracks. I don't know if my perception was changed because we were so knackered, but you lay down and it just sucked you in and you fell asleep really, really quickly. And got a good night's sleep too.