What is your model Apple TV box? Identify your Apple TV model - Apple Support
Your Mac and iPhone may have wider support for media formats than your Apple TV box (or AirPlay). Your files need to conform to all of these. I’d recommend H.264 video with AAC audio in an MP4/MOV/M4V container, with video resolution not exceeding the resolution for the Apple TV box and TV, and no more than 1080p, and no more than 30 fps. H.264 has a lot of encoding options, and possibly some property values may be out of bounds for AirPlay. AirPlay to older models Apple TV may require media file writing with QuickStart pseudo streaming properties (e.g. meta data at the start of the file, instead of at the end, and proper interleaving in small chunks); always advised, but not mandatory for newer models.
If you need to re-encode, then use a tool with Apple TV presets, if possible. E.g. HandBrake or ff·Works.
If you want to try optimizing/re-muxing without re-encoding, which is much faster, then use e.g. Subler. It won’t fix for codec incompatibilities, though.
Video formats and audio formats supported for the various models Apple TV box’s default media player, are listed in the technical specifications:
Apple TV (2nd generation) technical specifications - Apple
Apple TV (3rd generation) technical specifications - Apple
Apple TV HD (4th generation) technical specifications - Apple
Apple TV 4K (1st generation) technical specifications - Apple
Apple TV 4K (2nd generation) technical specifications - Apple