I don't know why, but I had an urge to use the genitive here. Is wolałby mieć innej pracy possible as well, or is that outright wrong?
In affirmative phrase it is plainly wrong. The verb "mieć" requires noun in accusative.
But in phrases with negation, the accusative is replaced by genitive: "On nie wolałby mieć innej pracy".
innej pracy