Remove some of the uses of Either

Work a bit towards #9157 "Remove Either". These instances don't need to use Either and are better expressed in other ways (removing allocations and simplifying types).