Okay, so I figured it out. The problem with the video players was user error (whoops!), but I'll post what I did to get things working to save some frustration for future users.
My big problem was my custom theme that hooks into my Wordpress install. If you're using a Wordpress header, you need to make sure that you have this line in your Wordpress header.php file:
`<?php if (function_exists('zenJavascript')) zenJavascript(); ?>`
As far as video encoding goes, I tried FLV but I couldn't get the files to come out looking very good. I ended up having really good results on my Mac by doing the following:
1. Output the video files at high resolution from [insert fancy program here — I was using After Effects] as MOV files.
2. "Export" the files using Quicktime Pro to scale down the files to the correct size but leave the files as a MOV files — I did not have good luck using Quicktime Pro to make mp4s. QP seemed to wash out the color from the files.
3. Open the exported files in Handbrake and set the video settings to h.264, 700kbps, 2-pass encoding, turbo first pass.
This gave me really small, beautiful looking files. I hope this helps someone else.
EDIT: Oh, and when you change the preferences for the flowplayer3 video size, make sure you add 25px to the height to account for the video player control bar.