Should all machines which run mongo instances (mongod or mongos) in a Mongo DB cluster have unique hostnames (also at OS level)?
Actually, it is a Very Bad Idea™ to do a load balancing this way with MongoDB. First of all, you can give multiple mongos instances to the driver. If one mongos goes down or becomes unavailable due to overload, the driver will be happy to access the next available mongos. Second, the config servers and mongod instances get unnecessary load for continuously updating the cluster "map". Third, they most likely will initiate and tear down connections continuously, too.

The solution would be to use CNAMEs at the DNS level instead of multiple A records for a host, but maintain unique hostnames on the OS level. That is, the hostname command should return a unique value on every host of the cluster, including the mongos instances.

A word on DNS based round robin load balancing: It's crap when used on it's own. You don't have any control over the load actually sent to each of the balanced servers. In case you have caching DNS servers between you and your biggest group of unique users, you actually might worsen the load for an individual server. You better use a "real" loadbalancer in front of your servers, something like HAProxy, varnish or nginx (depending on your application). In case you need / want to have more than one of those, you can use DNS based round robin load balancing on these, though from my experience, it is better to make one load balancer highly available to prevent a single point of failure.