If you’re playing from Google Photos or Flickr, those videos have been re-encoded to be compatible with almost all devices. Typically playback issues with these are rare unless bandwidth issues arise.
If you’re playing videos from Google Drive, Dropbox, or OneDrive for Business, your video is being played directly, byte for byte as it exists on the cloud drive, so you need to ensure the video is appropriate for your device. Please check your playback device is capable of playing back your videos. In general, don’t expect a 1080p device to natively decode 4K video streams or expect h.265 decoding from older devices.
Next, are the videos vertical or horizontal? Phones may encode vertical video as a horizontal video and then require the decoder to rotate it back to vertical. The Fire TV video decoder does not support doing this rotation so it must happen in software and this can tax the CPU.
Next, ensure your video file size / time in seconds is not greater than 3.5 MB/s (which is the max speed of a 2.4Ghz WIFI connection). If it does require more than that, you’ll need a 5Ghz wifi connection that is really connecting at 5Ghz.
If possible, try to keep video sizes under half of what your bandwidth supports. Cloud drives are not video streaming services. They do not guarantee your bytes will arrive consistently and on time. Alternatively, you could also use a service like Flickr or Google Photos or OneDrive (non-business), which will automatically convert and stream everything in a compatible MP4 format. They are closer to video streaming services.
If all else fails, have you tried using VLC for playback? It may work better or worse, depending on software vs hardware decoding, etc. You can install VLC and then enable VLC playback at the very bottom the app settings -> display. If that doesn’t help, disable it so you’re not stuck using VLC.