The Android based player plug-in has pretty good support. I’d recommend H.264 encoded .mp4 files. You won’t be able to play this same file inside the Editor though, because the Windows based player plug-in doesn’t support H.264 yet (but it will work when you run on device).
The only format that works on both Android and Windows is MPEG-4 encoded .mp4 files, but the quality will be much worse.
In general, 360 video is not supported very well right now, because of performance limitations. I am currently refactoring the Media Framework to address these and other issues.