I have rented a VPS and it will be used as a LAMP server.
I like using latest versions of LAMP packages and applying updates to them using yum rather than 'compile from source'.
As you may already know, for example, installing the latest version of PHP requires adding an extra repository such as the remi on CentOS, while the official repository for Fedora already includes the latest versions of LAMP packages.
The VPS only has 256mb RAM. Which OS should be chosen?
when you want to go with the last versions, you should use fedora. centos/rhel is made for long time, stable use. there won't be the latest versions updates included, only updates for fixing bugs.
Fedora no longer have a "Server" edition, and you will find the default edition is very large and contains a number of programs aimed at the desktop user. Last version I installed also had SELinux enabled, which produced errant behaviour and took some digging to find out!
If you are happy with RHEL administration I would install CentOS and upgrade using remi's repos as you will have much less initial configuration to do. Of course if your VPS hosts will install it for you then there's not really much comparison, and Fedora's ease of upgrade would probably win.
edit: With regards to the latest versions of software, as the question notes remi's repos will keep you up to date.
The difference between CentOS and Fedora is "Stable" v.s. "Bleeding edge". So if you want a server to experiment on: Go for Fedora and be prepared to reinstall every year or so.
If you want a 'stable' server with additional tools: Go for CentOS and add the mentioned remi and perhaps even the EPEL repository (which is basically useful Fedora stuff back-ported to RHEL/CentOS).