Greyball is just the tool they used to keep from getting caught.
The shady part is that they operate in cities were they aren't welcome (by city officials at least, customers and drivers seemed to welcome them with open arms). If Uber operating in Portland is a night burglar, Greyball is his dark clothes and mask.
Using a tool to avoid getting caught is, itself, evidence that one is aware of the impropriety of the action thereby protected.
Many view this kind of awareness as increasing the shadiness of the underlying action.
(And it mostly only applies to acts that, while perceived as shady, wouldn't be perceived as outright evil on their own -- no one thinks that something that is unquestionably murder on its own is more evil because you tried to conceal it [0], but if you are taking your co-workers' food out of the fridge, the idea that it wasn't intentional wrongdoing is harder to maintain when you're also caught stashing the wrappers in someone else's trash.)
[0] "No one" is a dramatic exaggeration, of course, and this assumes that the acts done in concealment aren't evil on their own, etc., etc.
Second, privacy has nothing to do with it, this is not an information we talking about, but a service. A bit like dealing weed/prostitution/etc and actively looking if there isn't any cop around.
* even if it is simply by adapting pre existing infrastructure created for a benign purpose
Government have to work that way. If lying to and evading regulation wasn't illegal, no regulation at all would be possible.