Having said that, I haven't run it on my linode, but I'm sure that Chris has taken away a lot of packages that you don't need. Because of the nature of a linode, you could always just make a disk image with ubuntu on it and test it out see how you like it and delete it if you don't.
The obvious difference to Debian is that Ubuntu releases much more often (every 6 months, I think), and thus they have, in general, much more recent versions of packages. /troll
So, Chris, should I (not a Debian guru) go with Ubuntu rather than Debian small? I suppose Ubuntu can use the same apt sources as Debian, right?