I need to order a new server for hosting a PostgreSQL 8.4 database, however I have to choose between Ubuntu 9 or 10: which one would be better / any special caveat with one or the other?
You should choose Ubuntu 10.04 since it's a LTS (Long Time Support) release, which means it a really stable distro shipped with only stable software. Adding that you have support until 2015-04 for the server (that include security patches, and so on).
It comes with postgresql 8.4.6. However if you need the new release postgresql 9.0 you can install on lucid following this tutorial.
If you are referring to 9.10 and 10.04 releases, choose the 10.04 as it is LTS, the LTS release is recommended for production systems.
Watch out for the file system used with PostgreSQL, there has been some regression in the performance of PostgreSQL using the ext4 file system in the past, so check if this is still the case.