My VPS provider serves Ubuntu 10.04 or CentOS 5.5. What are the major pros and cons for a VPS newbie?
Both of these are fairly cutting-edge distros. CentOS is of the Redhat family, Ubuntu of the Debian family of distros. The versions you mention are in fact not the latest, e.g. Ubuntu is now on 11.04 (however, I believe their 10.04 release was a long term support release, which may be the reason for your provider to use it).
As far as your choice is concerned, my advice would be to go with what you know best. There's little point in experimenting with too many variables at the same time.
It's generally always, pick what you know best and whichever is most stable if its for a production site.
I would also recommend Debian if its available, as ubuntu's server edition is not as good as its desktop edition, but its all down to personal preference and Debian tends to be the leanest in memory usage and most stable of the 3 with the con however that it sometimes falls behind on package versions. but it does tend to be the distro that has the most guides available for it
CentOS would then probably be my second choice after Debian. and is probably the most widely used linux distribution on servers thanks to red hat and Cpanel.
It's going to be a difficult answer other than that because its quite subjective to people's preferences, so my advice is as simple as wolfgangsz' pick what you know best.