But you can always root your phone and install Cyanogenmod from scratch, right? Agreed that this is not too trivial right now because of standardization issues, but it could be done if you really care about privacy.
This isn't true. You can stick to app repositories like F-Droid and use Raccoon to download Play Store apps via your desktop without using a Google account on your phone.
I don't use them personally but I imagine Goole Now, GMail and Google Maps would need Play Services.
The apps I do use (non-google) tend to function well enough without Play Services though.