They are marketed as two different products. Technically CN has a few more attributes in it that marginally improves routing. Previously Garmin have used CN for their more expensive products and CS for the cheaper ones. The reason for the existance of two different products are probably due to Navteq (map provider) licensing/pricing of the data.
The rumour right now (Garmin allegedly have said it to customers) is that with the upcoming upgrade to version 8 CitySelect will dissapear and that CS-customers will be forced to CityNavigator if they want version 8.
Update CD's are always free from Garmin but to be able to use the update you need to pay for the unlock code anyway.
Right now maybe isn't the smartest time to do an upgrade unless you really, really need it at this absolute moment. Having paid for an upgrade to version 7 will not be very fun the moment version 8 is out, which should be any day now. Keep an eye on this page to see when version 8 arrives and other details about the upgrade:
http://www.garmin.com/unlock/update.jsp