Can anyone tell me if a non-profit utility company that is owned by a city government can start a 401k? I think that they can do a 457, but they would prefer to do a 401k.

Probably not. In most instances, such an entity would be treated as a governmental plan. Thus, unless that entity, or another entity treated as part of the same "employer" for federal tax purposes, had a grandfathered 401(k) plan, the entity could not start a 401(k) plan.