I would go with cyanogenmod. They add features to stock android but are very particular about making sure the extra features feel as if they shipped with the device stock and add a lot more polish than other roms. They also value stability more than even vanilla aosp roms in my opinion. IF you want to get a galaxy s3 to run cm, make sure you buy the snapdragon version and not the exynos version. Same goes for the s4. The snapdragon versions are supported very well. (the snapdragon gs4 will essentially have perfect cm once the nexus edition is release) The exynos version is a hacked mess and cyanogen (himself) doesn't even officially support it.
If you get a nexus 4, unlock the bootloader first thing so that if you decide to flash a rom like CM (which I recommend doing), you won't have to wipe your internal storage. (you should still wipe your app data/settings partition). That way you won't lose your photos/music/documents. CM definitely improves the nexus devices immensely. If you want more features I recommend AOKP (heavily influenced by CM) over the alternatives. Paranoid is too buggy at the moment to recommend.
I run CM10.1 on my Galaxy Nexus and run AOKP 4.2.2 on my Nexus 7. The stability of both roms on nexus devices is excellent and no worse than stock. I actually would put cm10.1 a step above stock for stability.