Before CPUs, those symptoms would be from idle mixture too lean -giving hunting. The very good fuel consumption is confirming evidence.
The fix would be to set a touch richer and higher idle RPM. Nowadays with CPUs it is not so easy, yes it may be a faulty sensor. This should be a problem a decent tuner/workshop would be able to fix.