As of today, 156 days since I last rebooted my linode-96. Even then, it was just to change a kernel or something (don't remember now). It's been significantly longer since I've had to reboot for something significant. It's been rock solid and stable, and functions flawlessly as a small web and mail server. For the same amount of money that I was paying to another hosting company, I get more storage space, more bandwidth, and of course I get ROOT! :)
I definitely recommend the service. I've been very happy with it.